Smallest Range Covering Elements from K Lists
Last Updated: April 4, 2026
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. Think of it like tuning a radio dial: you need to find the narrowest frequency band where you can pick up a signal from every station.
The tricky part is that elements come from different lists, so we can't just use a simple sliding window on a single array. We need a strategy that considers elements across all k lists simultaneously. The key observation is that any valid range must start and end at elements that actually appear in the lists. So the answer range [a, b] always has a and b as values from the input.
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→ Standard comparison-based methods are the way to go.
Approach 1: Brute Force (Check All Pairs)
Intuition
The most direct approach: flatten all elements into a sorted array (tagged with their list index), then for each possible starting element, expand outward until all k lists are covered. This is essentially trying every element as the left boundary of the range and finding the smallest right boundary that covers all lists.
This approach is straightforward but involves redundant work. For each starting point, we re-scan forward to build 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.
For each starting index, we rebuild the coverage set from scratch. What if we maintained a sliding window instead, keeping track of which lists are covered as we expand and shrink?
Approach 2: Sorting + Sliding Window
Intuition
Here's the key insight: flatten all elements into one sorted array (keeping track of which list each came from), then use a sliding window to find the smallest window that contains at least one element from every list.
This is essentially the "minimum window substring" pattern but applied to sorted numbers with list membership instead of characters. We expand the right end of the window until all k lists are represented, then shrink from the left to minimize the range, then expand again.
Because the array is sorted, the range of any window [left, right] is simply sorted[right] - sorted[left]. We want to minimize this while covering all k lists.
The sorted order guarantees that within any window [left, right], the range is sorted[right] - sorted[left]. By expanding right to cover all k lists and then shrinking left to find the tightest valid window, we explore every possible minimal range. The sliding window never misses a valid configuration because every valid range must include some leftmost element, and we consider every element as a potential left boundary.
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), but the input lists are already sorted individually. What if we leveraged that sorted structure with a min-heap to avoid re-sorting entirely?
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 is perfect for this. We insert one element from each list, always know the current minimum (heap top), track the current maximum separately, and repeatedly pop the minimum and push its successor from the same list.
The min-heap approach works because of a greedy observation: the only way to potentially shrink the range is to increase the minimum. By always advancing the list that contributed the minimum, we systematically explore all possible "frontier" configurations. Every valid minimum range must be encountered during this process because the optimal range's lower bound must be a current minimum at some point, and when it is, the corresponding maximum is the smallest possible maximum given those pointer positions.
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).