Coding Interview PatternsSmallest Range Covering Elements from K Lists
HardK-way Merge
Smallest Range Covering Elements from K Lists
Explanation & Solution
Description
You have k lists of sorted integers. Find the smallest range [a, b] such that there is at least one integer from each of the k lists.
Among all the ranges, choose the range with the smallest gap b - a. If there are multiple answers, return the one with the smallest a.
Input: nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]]
Output:[20,24]
0
20
1
24
Explanation: [20,24] covers 24 from list 0, 20 from list 1, and 22 from list 2.
Constraints
nums.length == k1 <= k <= 35001 <= nums[i].length <= 50-10^5 <= nums[i][j] <= 10^5nums[i]is sorted in ascending order.
Approach
K-way Merge pattern
1. Seed the Min-Heap and Track Maximum
- Push the first element of every list into a min-heap as
[value, listIndex, elementIndex] - Track
maxVal— the largest value currently in the heap - The current range is always
[heap[0], maxVal]
2. Evaluate the Current Range
- At each step the heap minimum is
heap[0][0]and the maximum ismaxVal - If
maxVal - minVal < rangeEnd - rangeStart, update the best range
3. Advance the List That Owns the Minimum
- Replace the root with the next element from the same list and sift down
- Update
maxValif the new element is larger - This is the only move that can shrink the range — pulling a larger value up from the list with the current minimum
4. Stop When Any List Is Exhausted
- If the list owning the minimum has no more elements, we cannot cover all lists with a smaller range
- Break and return the best
[rangeStart, rangeEnd]found
Key Insight
- At every step the heap holds exactly one element per list. The current range
[min, maxVal]is the tightest possible window given the current selection — advancing the minimum is the only way to potentially improve it
Time
O(N log k) where N is total elementsSpace
O(k) for the heapVisualization
Input:
[4,10,15,24,26, 0,9,12,20, 5,18,22,30]
—
No animation available
Left (L)Right (R)ConvergedDone
0 steps