Smallest Range Covering Elements from K Lists
Understanding the Problem
We're given k sorted lists and need to find the tightest window (smallest range) such that at least one element from every list falls inside that window. The result is like tuning a radio to the narrowest frequency band that still picks up a signal from every station.
Elements come from different lists, so a single sliding window over one array does not directly apply. We need a strategy that considers elements across all k lists at once. Any valid range must start and end at values that actually appear in the lists, since shrinking the range to a non-existent boundary only loses coverage. So the answer range [a, b] always has both a and b equal to some input element.
Key Constraints:
1 <= k <= 3500and1 <= nums[i].length <= 50→ The total number of elements across all lists is at most 175,000. This is manageable for O(n log n) or O(n log k) approaches.nums[i]is sorted in non-decreasing order → Each list is already sorted. We can exploit sorted order with pointers or a min-heap to process elements in order.-10^5 <= nums[i][j] <= 10^5→ The widest possible range is2 * 10^5, which fits comfortably in a 32-bit integer, so range subtractions never overflow.
Approach 1: Brute Force (Check All Pairs)
Intuition
Flatten all elements into one array sorted by value (tagging each element with its list index), then try every element as the left boundary. For each left boundary, scan forward until all k lists are covered, which gives the smallest right boundary for that start. The smallest range over all starts is the answer.
The cost comes from redundant work: for each starting point we re-scan forward and rebuild coverage from scratch.
Algorithm
- Flatten all elements from all lists into a single list, tagging each with its list index.
- Sort this combined list by value.
- For each starting index
i, scan forward with indexjuntil all k lists have at least one element in the window[i, j]. - Record the range
[sorted[i], sorted[j]]if it's smaller than the current best. - Return the best range found.
Example Walkthrough
Code
- Time Complexity: O(n^2). We sort in O(n log n), then for each of the n starting points, we may scan up to n elements in the worst case.
- Space Complexity: O(n). The flattened sorted array stores all n elements, plus O(k) for the coverage set.
The wasted work is rebuilding coverage for every left boundary. A sliding window removes it by tracking coverage incrementally as the window expands and shrinks.
Approach 2: Sorting + Sliding Window
Intuition
Flatten all elements into one sorted array (keeping track of which list each came from), then slide a window that contains at least one element from every list. This is the "minimum window substring" pattern applied to sorted numbers, with list membership in place of characters. Expand the right end until all k lists are represented, then shrink from the left to minimize the range, then expand again.
Because the array is sorted, the span of any window [left, right] is sorted[right] - sorted[left]. We want to minimize that span while covering all k lists.
For each right, the inner loop advances left to the largest index that still covers all k lists, then records sorted[right] - sorted[left]. That records the smallest window ending at right. Since every valid window ends at some index, taking the minimum over all right covers every candidate, so the global minimum is found. The pass is linear because left only moves forward and never resets.
Algorithm
- Flatten all elements into a list of
(value, listIndex)pairs and sort by value. - Use two pointers,
leftandright, both starting at 0. - Maintain a frequency map counting how many elements from each list are in the current window, and a counter for how many distinct lists are covered.
- Expand
rightuntil all k lists are covered. - Once all k lists are covered, try shrinking from
leftto minimize the range. Update the best range if the current one is smaller. - Continue until
rightreaches the end.
Example Walkthrough
Code
- Time Complexity: O(n log n). Sorting takes O(n log n), and the sliding window pass is O(n) since each element is added and removed at most once.
- Space Complexity: O(n). The flattened sorted array stores all n elements, plus O(k) for the frequency count array.
The sorting step dominates at O(n log n), yet the input lists are already sorted individually. A min-heap reuses that structure with a k-way merge and avoids re-sorting, dropping the cost to O(n log k).
Approach 3: Min-Heap (Optimal)
Intuition
Since each list is already sorted, we can think of this as a k-way merge problem. Start by picking the first element from each list. These k elements define an initial range from min to max. Now, to try to shrink the range, we have two choices: increase the min or decrease the max.
Decreasing the max isn't useful because we'd need to go backward in a sorted list, which would only make the range larger or keep it the same. But increasing the min makes sense: we advance the pointer in the list that contributed the current minimum to its next element. This gives us a new candidate minimum, and the range might shrink.
A min-heap supports this directly. Insert one element from each list, read the current minimum at the heap top, track the current maximum separately, then repeatedly pop the minimum and push its successor from the same list.
At every step the heap holds one pointer per list, so each configuration is a valid covering set, and its range is currentMax - heapTop. Advancing the list that holds the minimum is the only move that can reduce the range, because raising any other pointer leaves the minimum and maximum unchanged or larger. This sweeps the left boundary through every input value in increasing order, and for each left value the maximum recorded is the smallest possible given the pointers so far. The optimal range's lower bound appears as a heap top at some step, so its range is checked.
Algorithm
- Initialize a min-heap with the first element from each list, tracking
(value, listIndex, elementIndex). - Track the current maximum across all elements in the heap.
- The current range is
[heap_top, currentMax]. - Pop the minimum element. If its range is better than the best seen, update the result.
- Push the next element from the same list (if it exists). Update currentMax if needed.
- Stop when any list is exhausted (we can't cover all k lists anymore).
Example Walkthrough
Code
- Time Complexity: O(n log k). Each of the n total elements is pushed and popped from the heap at most once, and each heap operation costs O(log k) where k is the number of lists.
- Space Complexity: O(k). The heap always contains exactly k elements (one from each list).