DSA problem
Smallest Range Covering Elements from K Lists
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] to be smaller than range [c, d] if b - a < d - c or a < c if b - a == d - c.
A brute-force search across all combinations of one element per list explodes combinatorially, so we need a smarter sweep. The crucial observation is that at any moment during a left-to-right sweep across all lists combined, if we keep a "frontier" of exactly one element per list, then the smallest and largest values among those frontier elements define a range that, by construction, includes at least one number from every list.
To find the optimal range we want to minimize max - min over all such frontiers. We can maintain the frontier with a min-heap of size k: pop the smallest value, record the range [min, max] if it improves on the best seen so far, then advance that list's pointer and push the new value. We must track the current maximum across the frontier separately because the heap only gives us efficient access to the minimum.
The sweep terminates as soon as one list is exhausted: at that point we cannot keep a representative from every list, so no further valid range can be formed. The total work is O(N log k) where N is the total number of elements across all lists — each element is pushed and popped exactly once — and the auxiliary space is O(k) for the heap.
This problem is a clean application of the K-Way Merge pattern: it walks through the merged sorted view of all lists while extracting an answer that depends on the simultaneous frontier, not on any single merged element.
Examples
nums = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]][20,24]nums = [[1,2,3],[1,2,3],[1,2,3]][1,1]nums = [[10,10],[11,11]][10,11]Constraints
- nums.length == k
- 1 <= k <= 3500
- 1 <= nums[i].length <= 50
- -10^5 <= nums[i][j] <= 10^5
- nums[i] is sorted in non-decreasing order.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.