K-way Merge — Smallest Range Covering Elements from K Lists
↗ LeetCode: Smallest Range Covering Elements from K Lists · Hard · pattern chapter →
Given k sorted lists of integers, find the smallest range [a, b] that contains at least one element from each list. If multiple, return the one with smaller a; if still tied, smaller b.
Example 1 — lists = [[4,10,15,24,26],[0,9,12,20],[5,18,22,30]] → [20, 24] (24-20=4) Example 2 — lists = [[1,2,3],[1,2,3],[1,2,3]] → [1, 1]
Constraints — 1 ≤ k ≤ 3500; total elements ≤ 5·10⁴. Brute enumerates every k-tuple across lists — O(prod-of-lengths) explodes past k=10. Min-heap of one-per-list + sliding-window max is O(N log k) = ~10⁶ ops at total N=10⁵.
Interview timer00:00
Approach 1 — Merge, sweep with sliding window on tagged list
Intuition. Merge all values with (value, listId) tags; sort by value; slide a window over the merged sequence containing at least one from every list; track shortest.
Complexity — Time O(N log N) for sort; Space O(N).
Approach 2 — Min-heap sweep (canonical)
Insight from merge. We only need to know the current minimum across all lists (candidate a) and track the current max (candidate b). A min-heap containing one pointer per list serves this.
- Init: heap of
(lists[i][0], i, 0); trackmaxSeeninitially = max of all first elements. - Loop: pop min → it's the current
a. Range[a, maxSeen]is a candidate. - Advance pointer in that list; push next; update
maxSeen. - Stop when a list is exhausted (we can't cover it anymore).
int[] smallestRange(List<List<Integer>> lists) {
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
int maxSeen = Integer.MIN_VALUE;
for (int i = 0; i < lists.size(); i++) {
pq.offer(new int[]{lists.get(i).get(0), i, 0});
maxSeen = Math.max(maxSeen, lists.get(i).get(0));
}
int[] best = {-100000, 100000};
while (true) {
int[] top = pq.poll();
int a = top[0];
if (maxSeen - a < best[1] - best[0]) { best[0] = a; best[1] = maxSeen; }
if (top[2] + 1 == lists.get(top[1]).size()) break;
int next = lists.get(top[1]).get(top[2] + 1);
maxSeen = Math.max(maxSeen, next);
pq.offer(new int[]{next, top[1], top[2] + 1});
}
return best;
}Complexity — Time O(N log k) where N = total elements; Space O(k).
Try it yourself
Complexity summary
| Approach | Time | Space | Interview grade |
|---|---|---|---|
| Merge + sliding window | O(N log N) | O(N) | acceptable baseline |
| Min-heap sweep | O(N log k) | O(k) | canonical |
When to use which
- Standard k-way merge with "cover all" requirement → min-heap sweep.
- Lists arrive as streams (unknown length) → same min-heap works; break on any list exhausted.
- "Range covering ≥ m of k lists" → generalize; needs a multi-set or ordered map.
- Instead of range: find k-th smallest overall → still min-heap sweep, just count pops.
Related problems
- Merge k Sorted Lists — same heap-sweep
- Ugly Number II — heap merges 3 streams
- Median of Two Sorted Arrays — 2-list balance BS