Pattern 13: K-way Merge

Deep Dive: Merge K Sorted Lists with a Min-Heap

Three sorted lists: [1,4,5], [1,3,4], [2,6]

Heap: [(1,list0), (1,list1), (2,list2)]

Pop (1,list0) -> result=[1], push 4 from list0. Heap: [(1,list1),(2,list2),(4,list0)]
Pop (1,list1) -> result=[1,1], push 3. Heap: [(2,list2),(3,list1),(4,list0)]
Pop (2,list2) -> result=[1,1,2], push 6. Heap: [(3,list1),(4,list0),(6,list2)]
Pop (3,list1) -> result=[1,1,2,3], push 4. Heap: [(4,list0),(4,list1),(6,list2)]
Pop (4,list0) -> result=[1,1,2,3,4], push 5. Heap: [(4,list1),(5,list0),(6,list2)]
Pop (4,list1) -> result=[1,1,2,3,4,4], list1 done. Heap: [(5,list0),(6,list2)]
Pop (5,list0) -> result=[...,5], list0 done. Heap: [(6,list2)]
Pop (6,list2) -> result=[1,1,2,3,4,4,5,6]. Done!

Why O(N log K): N total elements, each push/pop is O(log K) where K is the number of lists. The heap always has at most K elements.

---

Signal: Merge K sorted lists/arrays/streams into one sorted output Template: Min-heap of head elements

When to Use

• "Merge K sorted lists"
• "Smallest range covering elements from K lists"
• Any problem with K sorted sources to merge

Key Idea

Push the first element of each list into a min-heap: (value, list_index, element_index)
Pop smallest, add to result, push next element from same list.
Repeat until heap is empty.

Re-solve (TIMED)

Problem	Source	Target Time	Done?
Merge K Sorted Lists	Phase 1.8	20 min	[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

---

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

• "Merge K sorted lists / arrays / streams" into a single sorted output — the canonical statement.
• "Smallest range covering at least one element from each of K sorted lists" — a min-heap holding the current head of each list is the engine.
• "Kth smallest element in M sorted rows / sorted matrix" — heap of row-heads, pop K times.
• "Multiple sorted sources where you want the next-smallest globally without merging upfront" — heap-of-heads pattern, useful for infinite or huge streams.

Anti-signals (looks like this pattern, isn't)

• "Merge two sorted lists" — the two-pointer merge step is enough; the heap is overkill for K=2.
• "K largest elements from one array" — Top-K pattern (single size-K heap), not K-way merge.
• "Sort a small concatenation of K sorted lists" — sometimes sort(concat(lists)) is fine; reach for heap-merge when K is large or the streams are infinite.