1Understand
The idea
Put the first element of each sorted list in a min-heap. Repeatedly pop the smallest, output it, and push the next element from the same list. The heap never holds more than k items, so merging N elements costs O(N log k).
Intuition
Put the first element of each sorted list into a min-heap (value, list id, index). Repeatedly pop the smallest, emit it, and push the next element from the same list. The heap never holds more than k items.
Merging N total elements costs O(N log k), much better than comparing all heads in O(Nk) if you rebuild without a heap, or concatenating and sorting in O(N log N).
The same pattern merges k sorted arrays or runs in external sort.
What you will be able to do
- Push a tie-breaker so tuples compare
- Advance only the list that was popped
When to use it
- Merge k sorted lists or arrays
- K-th smallest across sorted rows
2See it
Walkthrough
Merge k sorted lists
Lists [1,4], [2,3], heap of current heads.
1 / 5
Seed heap with (1, list0), (2, list1). Tuple compare uses value first.
Live template
Complexity: time O(N log k), space O(k)
O(N log k) time, O(k) heap space plus the output. Pairwise merge of lists can match O(N log k) with careful ordering. Concatenate + sort is simpler but O(N log N) and loses the benefit when k is tiny.
Read the walkthrough as text
Merge k sorted lists. Lists [1,4,5], [1,3,4], [2,6].
- Heap seeded with
(1,0,0),(1,1,0),(2,2,0). - Pop
(1,0,0), emit1, push next from list 0:(4,0,1). - Pop
(1,1,0), emit1, push(3,1,1). - Continue until heap empty →
1,1,2,3,4,4,5,6.
Store list index in the tuple so equal values compare safely in Python 3.
3Recognise it
Kinds of problems (4)
Same pattern, different surfaces. Each row is a problem shape you should recognise, not only the first walkthrough example.
Merge k sorted lists
Example. Return one sorted list from k sorted linked lists.
How. Min-heap of (value, list index, next index); pop, append, push successor from that list.
K-th smallest in a sorted matrix
Example. K-th smallest among rows sorted left-to-right.
How. Heap seeds first column (or row) heads; k pops give the answer.
Smallest range covering k lists
Example. Minimum [min,max] span including one element from each list.
How. Heap tracks current max; shrink left by advancing the list that held current min.
K smallest pair sums
Example. K smallest sums ai + bj from two sorted arrays.
How. Heap of (sum, i, j) starting at (0,0); push (a[i]+b[j+1], i, j+1) and (i+1,j) on pop.
Common mistakes
Failure modes the tutor watches for. Open the Common mistake tab in the walkthrough to watch one fail live.
Uncomparable heap items
Why it happens. Tie values look identical so tuple compare should work.
How it fails. Heap of TreeNode objects without (val, i, j), TypeError when two nodes compare equal.
Fix. Push comparable tuples: (value, list_index, position) as tie-breaker.
Concatenate and sort
Why it happens. Concatenate all lists and sort once is simpler code.
How it fails. k=100 lists of length m: O(km log km) concat-sort vs O(km log k) merge, TLE.
Fix. Heap-merge heads only; each element pushed/popped once.
Empty inputs
Why it happens. Initialization loops over all lists blindly.
How it fails. Push (lists[i][0], i, 0) when lists[i] is empty, IndexError before first pop.
Fix. Only seed heap from non-empty lists (`if lst:`).
4Check yourself
Concept check
A short quiz on this lesson before you practise. Optional, and it does not gate coding.
Ready to practise?
Mastery comes from solving. The lesson is optional context.