K-way merge

42 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Three sorted lists: A = [1, 4, 5], B = [1, 3, 4], C = [2, 6]. Merge them into one sorted list. By hand you look at the first element of each list, pick the smallest, write it down, and cross it off. Then look at the new firsts again. With three lists that is a glance at three numbers each time. With k = 10,000 lists, each pick means scanning 10,000 front elements, and there are N picks in total (one per element across all lists), so about N × k looks. For 10,000 lists of 10,000 elements that is a trillion.

The wasteful part is clear: between picks, only one list's front changes, yet we rescan all of them. We need something that remembers the fronts and finds the smallest without a full scan.

Build the structure, one piece at a time

Piece one: a min-heap holding one entry per list: (front value, which list, position). The heap always shows the smallest entry, which is the smallest front across all lists.

Piece two: the loop. Pop the smallest entry, append its value to the output. Then advance that list by one and push its new front, if the list is not exhausted. Every other list's entry sits untouched in the heap.

Piece three: the same loop works when the "lists" are implicit. A sorted matrix is a set of sorted rows. "Pairs with the smallest sums" from two sorted arrays is n lists, one per first element, each sorted by the second element. You push the first element of each list and generate the next on demand.

Why it is correct

The invariant: the heap contains exactly the current front of every non-empty list. Initially it holds every first element. Each step removes one front and replaces it with that list's next element, so the set of fronts is maintained.

next output = min over lists of (front of list) = top of the heap

Because each list is sorted, its front is its smallest remaining element, so the smallest front is the smallest remaining element anywhere. Appending it keeps the output sorted, and nothing smaller can appear later.

Why it is fast

Every element is pushed into the heap once and popped once. The heap never holds more than k entries, so each operation costs O(log k). Total O(N log k) for N elements overall, with O(k) extra memory. For 10,000 lists of 10,000 elements, that is about 10⁸ × 14 heap steps instead of a trillion scans. Concatenating everything and sorting would be O(N log N), which is worse when k ≪ N, and impossible for streams.

How to recognise it in an interview

"Merge k sorted lists", "kth smallest in a sorted matrix", "k pairs with the smallest sums", "smallest range covering one element from each list". The shared shape is several sorted sources and the need to consume them in global order. Say: "I will heap the front of each source and repeatedly pop the smallest and push its successor." Merge k Sorted Lists is this exactly on linked lists. Kth Smallest Element in a Sorted Matrix runs the loop k times over the rows. Smallest Range Covering Elements from K Lists keeps the same heap plus the current maximum, so that the range is max − min at every step.

02The idea in one line

Heap the head of each list; pop the smallest and push its successor.

Reach for it when: Merge k sorted lists, smallest range, kth smallest in sorted matrix, k pairs.

Cost: O(N log k) time.

03The walk-through, step by step

The video works one example: Merge [1,4,5],[1,3,4],[2,6]. These are its captions in order, so you can follow without the video or check a step you missed.

1. Seed the heap with the head of every list
2. Pop the smallest, 1 from A; push A's next, 4
3. Pop the smallest, 1 from B; push B's next, 3
4. Pop the smallest, 2 from C; push C's next, 6
5. Pop the smallest, 3 from B; push B's next, 4
6. Pop the smallest, 4 from A; push A's next, 5
7. Pop 4 from B; B is exhausted, nothing to push
8. Pop 5 from A; A is exhausted, nothing to push
9. Pop 6 from C; C is exhausted, nothing to push
10. Heap empty: output [1,1,2,3,4,4,5,6] is sorted
11. N elements, each through a heap of size k: O(N log k)

04Asked at Google

6 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Heap: Top-k with a size-k heap, Two heaps (running median), Greedy scheduling with a heap, Lazy deletion heap, Pop-k-then-rebuild (frequency greedy).