Coding · Heaps
Merge k Sorted Lists
- Reported once
- Hard
- 1 source
One candidate write-up. Treat it as a single data point.
Solve it in the playground, with tests
You receive k sorted lists of integers, any of which may be empty, and must combine them into one sorted list. For [[1,4,5],[1,3,4],[2,6]] the result is [1,1,2,3,4,4,5,6]. The total number of values N and the number of lists k can each reach about 10,000, so repeatedly scanning all k list fronts for every output value costs about N times k steps, which is wasteful and grows quickly. In the original problem each list is a chain of linked nodes that the answer should reuse; here the lists arrive as arrays, are turned into chains, and the merged chain is read back as an array.
Restated in our own words, not a quote from Netflix or any page. The answer below is written for this site.
Clarify first
Pin down the input before you touch the keyboard.
I ask how big k can be and how large the total number of nodes N is. Are the lists linked lists, and may I relink the existing nodes? Can lists be empty, and can k be zero? Are values possibly negative or repeated, and does the order of equal values matter? Is every input list truly sorted ascending? Is O(k) extra space acceptable?
Assumptions: k and N are around ten thousand, nodes can be relinked, empty lists are skipped, duplicates and negatives are allowed, ties may come out in any order because only the values are checked, and O(k) extra space is fine. I would also mention divide and conquer, which merges lists in pairs, as a heap-free alternative with the same time.
Brute force
Say the obvious answer and why it is too slow.
Brute force one: collect all N values, sort them, and rebuild the list. That is O(N log N) and ignores the fact that the inputs are already sorted, so each value pays log N when log k would do, and it does not reuse the nodes. Brute force two: for each output position, look at the front of all k lists and take the smallest. That costs O(k) per output value and O(N·k) overall. With k and N both near ten thousand that is a hundred million comparisons, and it keeps growing quickly with bigger inputs. A third idea, merging the lists one after another into a growing result, is also O(N·k) in the worst case, because the early lists get walked again and again. The heap removes the repeated scan across the fronts.
The insight
The one idea that makes it fast, and why it is correct.
- Brute force
- O(N·k)
- Time
- O(N log k)
- Space
- O(k) heap
The pattern is a min-heap over the current fronts. At any moment the next output value must be the smallest of the k front nodes, because every list is sorted and so nothing behind a front can be smaller than that front. If the k fronts sit in a min-heap, finding the smallest costs O(log k) instead of O(k).
The loop is: push the head of each non-empty list into the heap. Pop the smallest node and append it to the output chain. If the popped node has a successor, push it, because it is the new front of that list. Repeat until the heap is empty. The heap never holds more than one node per list, so its size is at most k.
Why it is correct: the invariant is that the heap holds the front of every list that still has unmerged nodes. The popped node is then smaller than or equal to every unmerged node, since an unmerged node is either a front, which is in the heap, or sits behind a front in a sorted list. Appending it is therefore safe. Each node is pushed once and popped once, so there are N pushes and N pops at O(log k) each.
Out loud: the heap is a tournament among the list fronts. I only ever compare k candidates, and replacing the winner with its successor keeps the tournament full. JavaScript has no built-in heap, so I would say that I am writing a small array-based one before I start coding it.
Walk it through
A dry run on the example, step by step.
| step | popped | pushed | heap now | merged so far |
|---|---|---|---|---|
| 0 | - | heads 1,1,2 | 1,1,2 | (empty) |
| 1 | 1 (list 0) | 4 | 1,2,4 | 1 |
| 2 | 1 (list 1) | 3 | 2,3,4 | 1,1 |
| 3 | 2 (list 2) | 6 | 3,4,6 | 1,1,2 |
| 4 | 3 (list 1) | 4 | 4,4,6 | 1,1,2,3 |
| 5 | 4 (list 0) | 5 | 4,5,6 | 1,1,2,3,4 |
| 6 | 4 (list 1) | none | 5,6 | 1,1,2,3,4,4 |
| 7 | 5 (list 0) | none | 6 | 1,1,2,3,4,4,5 |
| 8 | 6 (list 2) | none | (empty) | 1,1,2,3,4,4,5,6 |
Take [[1,4,5],[1,3,4],[2,6]]. The heap starts with the three fronts, 1, 1 and 2. Pop a 1 from the first list and push its successor 4; the output is 1. Pop the other 1 and push 3; the output is 1, 1. Pop 2 and push 6. Pop 3 and push 4. Now two 4s compete, and either may leave first since only the values are compared. Popping the 4 of the first list pushes 5; popping the other 4 pushes nothing. Then 5 leaves with nothing behind it, and 6 leaves last, emptying the heap. The heap column in the trace never holds more than three values, which is k, and the merged column ends with the answer.
The code
Runnable JavaScript, checked against test cases.
function mergeKLists(lists) {
const heap = [];
const swap = (a, b) => ([heap[a], heap[b]] = [heap[b], heap[a]]);
const push = (node) => {
heap.push(node);
let i = heap.length - 1;
while (i > 0 && heap[i].val < heap[(i - 1) >> 1].val) {
swap(i, (i - 1) >> 1);
i = (i - 1) >> 1;
}
};
const pop = () => {
const top = heap[0];
const last = heap.pop();
if (heap.length === 0) return top;
heap[0] = last;
let i = 0;
for (;;) {
let smallest = i;
for (const child of [2 * i + 1, 2 * i + 2]) {
if (child < heap.length && heap[child].val < heap[smallest].val) smallest = child;
}
if (smallest === i) return top;
swap(i, smallest);
i = smallest;
}
};
for (const values of lists) {
let head = null;
for (let i = values.length - 1; i >= 0; i--) head = { val: values[i], next: head };
if (head) push(head);
}
const dummy = { val: 0, next: null };
let tail = dummy;
while (heap.length > 0) {
tail.next = pop();
tail = tail.next;
if (tail.next) push(tail.next);
}
const merged = [];
for (let node = dummy.next; node; node = node.next) merged.push(node.val);
return merged;
}Runs here in your browser, in a sandboxed worker. Nothing is sent anywhere.
Try your own input
Write JavaScript that calls the code above and prints with console.log. It runs after the solution.
Edge cases
What to test before you say you are done.
- No lists: the heap stays empty and the result is an empty list.
- All lists empty: empty heads are never pushed, so the loop does not run.
- A single list: the heap holds one node at a time and the output equals the input.
- Duplicates across lists: the heap compares with strict less-than, so equal values simply stay where they are, ties come out in either order, and none are dropped.
- Negative values: only comparisons are used, so sign makes no difference.
- Very uneven lists: a long list simply keeps winning pops while short lists run out and leave the heap.
Follow-ups to expect
Where the interviewer pushes next.
- Can you merge the lists with divide and conquer instead, and what is its cost?
- What if the lists are too big for memory and arrive as sorted files on disk?
- How would you return only the smallest m values of the merged result?
- How would you merge k sorted streams that never end?
- How would you change the code so equal values keep the order of their lists?
Where candidates slip
The mistakes this problem punishes.
- Pushing a null head for an empty list, so the heap comparison fails on
null.val. - Forgetting to push the popped node's successor, which loses the rest of every list.
- Re-sorting an array of fronts after every pop. That is O(k log k) per value, worse than the heap.
- Returning the dummy head instead of
dummy.next. - Stating the time as O(N log N), when the heap has k entries and the correct bound is O(N log k).
- Writing a heap sift-down that compares only one child, which breaks the heap property.
Have a go before you read.
Interviews reward the sketch you make cold. Clarify out loud, draw it, then compare with the answer.
Now make it stick
Where this was reported
Public pages only. Companies do not confirm these, and they rotate their questions, so treat each link as one person's account or one list's tag.