K-Way Merge
Use a min-heap of k pointers (one per list) to merge k sorted sources in O(N log k).
Merge k sorted lists, smallest range covering k lists, kth smallest in a sorted matrix.
Each of the N total elements across k lists is pushed and popped once on a heap of size k. The heap holds at most one pointer/value per list.
A min-heap holding one pointer per sorted source lets you always know the global minimum across all sources in O(log k). Pop it, advance that source's pointer, push the next value from that source. Repeat until all sources are exhausted. Total work: O(N log k) where N is the total number of elements across all k lists.
The pattern generalizes the 2-way merge of mergesort. Crucially, it beats the naive 'concatenate-then-sort' (O(N log N)) whenever k < N, which is almost always. It's the right tool for external sorting: when data doesn't fit in memory, sort chunks, then k-way merge the sorted chunks back.
A common variant is 'smallest range covering k lists': maintain one pointer per list in a min-heap, also track the current max across the heap; the range [min, max] covers all k lists. Pop the min, advance, update max, repeat — shrinking the range whenever possible.
A min-heap of one pointer per source gives O(log k) access to the global minimum across k sorted streams, reducing the merge from O(N * k) (linear scan per pop) to O(N log k).
- Pushing all N elements into the heap up-front (O(N log N)) instead of maintaining only k pointers (O(N log k)).
- Forgetting to handle empty input lists, which would crash if you try to push their first element unconditionally.
- Using value-only heap entries when you need (value, listIdx, elementIdx) to advance the correct list after a pop.
- In 'smallest range', forgetting to update the running max when pushing a new element, returning a range that doesn't cover all lists.
- For 'kth smallest in sorted matrix', failing to use the row/column structure — you can use binary search on value for O(n log(max-min)) instead.
- Merge k sorted linked lists: heap of (val, listIdx) or divide-and-conquer pairwise merging.
- Kth smallest in sorted matrix: heap-based k-way merge of rows, or binary search on value.
- Smallest range covering elements from k lists: heap + running max.
- External sort: chunk-and-merge for data larger than memory.
// import java.util.*;
PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
for (int i = 0; i < lists.size(); i++) {
if (!lists.get(i).isEmpty()) {
pq.offer(new int[]{ lists.get(i).get(0), i, 0 });
}
}
List<Integer> merged = new ArrayList<>();
while (!pq.isEmpty()) {
int[] top = pq.poll();
int val = top[0], listIdx = top[1], elemIdx = top[2];
merged.add(val);
if (elemIdx + 1 < lists.get(listIdx).size()) {
pq.offer(new int[]{ lists.get(listIdx).get(elemIdx + 1), listIdx, elemIdx + 1 });
}
}
return merged;Problems using this pattern
2Easiest first · Blind 75 above NeetCode 150