Smallest Range Covering Elements from K Lists

Smallest Range Covering Elements from K Lists is a Hard Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Heap (Priority Queue) Patterns pattern, in the K-way Merge subpattern.

Problem statement

You have k lists of sorted integers in non-decreasing order. Find the smallest range that includes at least one number from each of the k lists.

We define the range [a, b] is smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.

Example 1:

Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] Output: [20,24] Explanation: List 1: [4, 10, 15, 24,26], 24 is in range [20,24]. List 2: [0, 9, 12, 20], 20 is in range [20,24]. List 3: [5, 18, 22, 30], 22 is in range [20,24].

Example 2:

Input: nums = [[1,2,3],[1,2,3],[1,2,3]] Output: [1,1]

Constraints:

- nums.length == k

- 1 <= k <= 3500

- 1 <= nums[i].length <= 50

- -105 <= nums[i][j] <= 105

- nums[i] is sorted in non-decreasing order.

Topics and companies

Topics: Array, Hash Table, Greedy, Sliding Window, Sorting, Heap (Priority Queue).

Reported in interviews at Amazon.

How to practise Smallest Range Covering Elements from K Lists on Thita.ai

Starter code is provided in C, C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(N log k), where N is the total number of elements across all lists and k is the number of lists. Each element is pushed and popped from the heap at most once, and heap operations take O(log k) time. time and O(k), for the min-heap which at any time contains at most one element from each of the k lists. space.

Open Smallest Range Covering Elements from K Lists in the code editor, or read the Smallest Range Covering Elements from K Lists editorial for a worked solution with its approach and complexity analysis.

Where Smallest Range Covering Elements from K Lists sits in the DSA pattern sheet

• Heap (Priority Queue) Patterns pattern guide
• K-way Merge subpattern
• The full DSA patterns sheet
• All coding practice problems

Problems related to Smallest Range Covering Elements from K Lists

Other problems that use the same K-way Merge and Heap (Priority Queue) Patterns techniques:

• Find K Pairs with Smallest Sums — Medium, same subpattern
• Kth Smallest Element in a Sorted Matrix — Medium, same subpattern
• Merge k Sorted Lists — Hard, same subpattern
• Finding MK Average — Hard, same pattern
• Find Median from Data Stream — Hard, same pattern
• Furthest Building You Can Reach — Medium, same pattern