K-Way Merge

TL;DR

Two-pointer merge of two sorted lists is the base case: at every step you compare the heads of both lists and emit the smaller one. K-way merge is the generalisation — instead of two cursors you keep K, one per input list, and the only question is “which cursor points at the global minimum right now?” Answer that with a min-heap of (value, list_idx, position) tuples and you get O(log K) per step.

Total work: N pops, each O(log K), so O(N log K) time and O(K) extra space — where N is the total number of elements across all K lists. This beats the naive “concatenate then sort” O(N log N) whenever K is much smaller than N, which is the entire point of the pattern.

The same skeleton solves three problems that look unrelated on the surface: merging K sorted linked lists, finding the kth smallest in a sorted matrix (treat each row as a list), and finding the smallest range that covers at least one element from every one of K lists (heap of cursors plus a running max).

When to reach for it

Signals that K-way merge is the right pattern:

• The input is multiple sorted streams — K linked lists, K arrays, K files on disk, K rows of a sorted matrix — and you need a single merged output (or just the kth element of it).
• The problem is “kth smallest in a sorted matrix” where rows and columns are individually sorted. Each row is a sorted stream; pop k times and return the last value popped.
• You need the smallest range (or smallest window) that touches every one of K sorted lists. The heap holds one cursor per list; the window is [heap_min, running_max].
• A naive solution flattens all N elements and sorts — O(N log N) — and you notice that within each list the order is already known, so most of that sort work is wasted.

Signals it’s not K-way merge: the streams aren’t individually sorted (use sort or quickselect), or K is so small (K = 2) that a plain two-pointer merge is simpler and avoids the heap overhead.

Flavor 1 — merge K sorted lists

Given K sorted linked lists, return one merged sorted list.

import heapq

def merge_k_lists(lists: list[list[int]]) -> list[int]:
    heap = []
    # seed: one cursor per non-empty list
    for i, lst in enumerate(lists):
        if lst:
            heapq.heappush(heap, (lst[0], i, 0))
    out = []
    while heap:
        val, i, j = heapq.heappop(heap)
        out.append(val)
        if j + 1 < len(lists[i]):
            nxt = lists[i][j + 1]
            heapq.heappush(heap, (nxt, i, j + 1))
    return out

The tuple (val, i, j) is the trick. val drives the heap order; i is the tiebreaker when two lists hold equal values (and also tells you which cursor to advance); j is the position inside list i.

Worked example. lists = [[1, 4, 5], [1, 3, 4], [2, 6]].

Heap size stays ≤ K = 3 throughout. Each of the N = 8 elements gets pushed once and popped once. Total: 8 · log 3 operations.

Flavor 2 — kth smallest in a sorted matrix

Given an n × n matrix where each row and each column is sorted ascending, find the kth smallest element.

import heapq

def kth_smallest(matrix: list[list[int]], k: int) -> int:
    n = len(matrix)
    heap = [(matrix[i][0], i, 0) for i in range(n)]
    heapq.heapify(heap)
    for _ in range(k - 1):
        val, i, j = heapq.heappop(heap)
        if j + 1 < n:
            heapq.heappush(heap, (matrix[i][j + 1], i, j + 1))
    return heap[0][0]

Each row is a sorted stream. Seed the heap with the first column, then pop k - 1 times — the kth pop’s value is the answer (peek at heap[0] instead of popping).

Worked example. k = 8 on:

 1  5  9 11
 2  6 10 13
 3  7 12 14
 4  8 15 16

Seed: [(1,0,0),(2,1,0),(3,2,0),(4,3,0)]. Pop sequence: 1, 2, 3, 4, 5, 6, 7 (7 pops, then peek). After each pop we push the next element of that row; e.g. popping (1,0,0) pushes (5,0,1). The 8th smallest is 8, which is heap[0][0] after seven pops. Total work: O(k log n), better than O(n²) when k is small.

Flavor 3 — smallest range covering K lists

Given K sorted lists, find the smallest range [a, b] such that at least one element from each list lies inside it.

import heapq

def smallest_range(lists: list[list[int]]) -> list[int]:
    heap = []
    cur_max = float("-inf")
    for i, lst in enumerate(lists):
        heapq.heappush(heap, (lst[0], i, 0))
        cur_max = max(cur_max, lst[0])
    best = [float("-inf"), float("inf")]
    while True:
        val, i, j = heapq.heappop(heap)
        if cur_max - val < best[1] - best[0]:
            best = [val, cur_max]
        if j + 1 == len(lists[i]):
            return best  # one list exhausted → can't shrink further
        nxt = lists[i][j + 1]
        cur_max = max(cur_max, nxt)
        heapq.heappush(heap, (nxt, i, j + 1))

The heap always holds exactly one cursor per list, so the window [heap_min, cur_max] always covers all K lists. Advancing the cursor that holds the minimum is the only move that can shrink the window — every other move would either keep the min the same or grow it.

Trace. lists = [[4,10,15,24,26], [0,9,12,20], [5,18,22,30]].

Answer: [20, 20]. Width 0 because 20 appears in list 1; lists 0 and 2 each straddle it.

Why it works — the invariant

At every iteration, the heap holds exactly one cursor per non-exhausted list, pointing at the smallest unemitted value in that list. Two facts follow directly:

1. heap[0] is the global minimum of all unemitted values, because every list’s smallest unemitted value is in the heap, and the heap surfaces the smallest of those.
2. Popping heap[0] and pushing the next element of that same list (and only that list) preserves invariant #1 — every other list still has its smallest unemitted value in the heap, and the popped list now has its new smallest in the heap too.

The smallest-range flavor adds a second invariant: cur_max ≥ every value in the heap, so [heap[0][0], cur_max] always covers all K lists. Advancing the min-cursor is the only move that can shrink the window without breaking coverage.

Complexity

• Time: O(N log K). Each of the N elements is pushed and popped from the heap exactly once; heap operations on a size-K heap are O(log K).
• Space: O(K) for the heap. The output (if you materialise it) is O(N), but the working set is bounded by the number of lists, not the total size.

The naive “flatten and sort” alternative is O(N log N). K-way merge wins whenever K ≪ N, which is the typical case (merging 10 files of a million records each, K = 10 vs N = 10⁷).

Common pitfalls

• Heap comparison failing on equal values. If you push (val, node) and two values tie, Python falls through to comparing the second tuple field — and ListNode objects aren’t comparable, so you get TypeError: '<' not supported. Always include a unique tiebreaker like the list index or a monotonic counter: (val, i, node).
• Advancing the wrong cursor. Only the popped list’s cursor advances. Iterating for lst in lists: lst.next after each pop is the classic bug — you’ll skip elements and produce a non-merged output.
• Pushing all N elements at once. Seeding the heap with every element from every list works but defeats the purpose: the heap is now size N, operations are O(log N), and you’ve reinvented sorted(flatten(lists)). The whole point is to keep the heap at size K.
• list.sort() instead of a heap. Calling cursors.sort() after each step gives O(K log K) per element and O(N · K log K) overall — strictly worse than O(N log K). Use heapq, not a sorted list.
• Forgetting the exhaustion check. Pushing lists[i][j+1] without checking j + 1 < len(lists[i]) raises IndexError on the last element of every list. In the smallest-range flavor, exhaustion is also the termination signal — miss it and you loop forever.

Where you see this in production

K-way merge is the engine of any system that has to combine sorted runs:

• External sort in PostgreSQL. When a query’s sort doesn’t fit in work_mem, Postgres spills sorted runs to temp files, then K-way-merges them with a tournament tree (logical equivalent of a heap of cursors). See tuplesort.c and the mergeruns path.
• LSM-tree compaction in RocksDB. Compaction reads multiple sorted SST files and merges them into a new level. The MergingIterator in RocksDB is a heap of per-SST iterators — exactly Flavor 1, with tombstone handling on top.
• Cassandra SSTable read path and compaction. A read may have to merge rows from several SSTables plus the memtable; Cassandra uses a MergeIterator over the sorted sources, again heap-of-cursors.
• MapReduce / Spark shuffle merge. Each reducer receives sorted shuffle outputs from many mappers and K-way-merges them before invoking the reduce function. Hadoop’s Merger and Spark’s ExternalSorter.merge are both this pattern.

Practice problems

Resources

• NeetCode roadmap — neetcode.io/roadmap — pattern-by-pattern problem sets organised exactly like this site.
• NeetCode practice grid — neetcode.io/practice — track which problems you’ve solved per pattern.
• NeetCode YouTube — @NeetCode — clear, whiteboard-style walkthroughs for almost every LeetCode problem above.