K-way Merge

K-way Merge

Merge k sorted streams via a min-heap of frontiers — one entry per stream. The foundation for kth-smallest across multiple sources, sorted-matrix queries, and external sorting.

7 problems 1 Easy 5 Medium 1 Hard

Merge k sorted streams in O(N log k) using a min-heap of one 'head' per stream. Pop the smallest, advance its stream, push the new head. Each element enters and leaves the heap exactly once.

The pattern generalizes to: kth-smallest across multiple sorted arrays, sorted-matrix queries, smallest-range-covering-all-lists, and external-memory merge sort. It also expresses itself as DP with k pointers (super-ugly-number), where each generator advances independently.

When to reach for this pattern

k sorted arrays / lists / streams to combine
kth smallest across multiple sorted sources
Sorted-by-row-and-column matrix queries
Smallest range that includes at least one element from each list

Canonical template

using P = tuple<int, int, int>; // (value, streamIdx, indexInStream)
priority_queue<P, vector<P>, greater<>> pq;
for (int i = 0; i < (int)lists.size(); ++i)
    if (!lists[i].empty()) pq.emplace(lists[i][0], i, 0);
while (!pq.empty()) {
    auto [v, s, idx] = pq.top(); pq.pop();
    emit(v);
    if (idx + 1 < (int)lists[s].size())
        pq.emplace(lists[s][idx + 1], s, idx + 1);
}

C++ · adapt the names and types to your problem.

Common pitfalls

Forgetting to advance the same stream after popping — emits duplicates or skips elements
Heap entries must carry stream identity (index), not just value, to know what to advance
Empty input streams crash if pushed unguarded — initialize only non-empty heads
On infinite streams, careful with termination — the heap will never empty

When to reach for this pattern

Canonical template

Common pitfalls

Related patterns

Problems (7)

Keyboard shortcuts