23. Merge K Sorted Lists
hardAsked at DRWDRW asks Merge K Sorted Lists as a direct proxy for order-book consolidation: merge k sorted streams of price-level updates — one per venue — into a single sorted output. The min-heap approach is expected; naive pairwise merging is rejected. Throughput analysis is a required companion question.
By Alex Chen, Founder, InterviewChamp.AI · Last verified
Source citations
Public interview reports confirming this problem appears in DRW loops.
- Glassdoor (2026-Q1)— DRW SWE onsite candidates report Merge K Sorted Lists as one of the canonical hard problems, directly connected to multi-venue order-book consolidation in follow-up discussion.
- Blind (2025-11)— DRW interview threads consistently list Merge K Sorted Lists as a must-prepare hard, with interviewers expecting both the heap approach and the divide-and-conquer alternative.
Problem
You are given an array of k linked-lists lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it.
Constraints
k == lists.length0 <= k <= 10^40 <= lists[i].length <= 500−10^4 <= lists[i][j].val <= 10^4lists[i] is sorted in ascending order.The sum of all lists[i].length will not exceed 10^4.
Examples
Example 1
lists = [[1,4,5],[1,3,4],[2,6]][1,1,2,3,4,4,5,6]Explanation: Merge three sorted lists into one.
Example 2
lists = [][]Explanation: Empty input.
Example 3
lists = [[]][]Explanation: Single empty list.
Approaches
1. Min-heap (priority queue)
Initialize a min-heap with the head of each non-null list. Repeatedly extract the minimum, append it to the result, and push the next node from the same list. Runs in O(n log k) where n is total nodes.
- Time
- O(n log k)
- Space
- O(k) heap
// JavaScript lacks a built-in heap; simulate with a sorted array for interview.
// In production, use a proper binary min-heap.
function mergeKLists(lists) {
const dummy = { next: null };
let curr = dummy;
// Heap entries: [node.val, listIndex, node]
const heap = [];
for (let i = 0; i < lists.length; i++) {
if (lists[i]) heap.push([lists[i].val, i, lists[i]]);
}
heap.sort((a, b) => a[0] - b[0]); // initial sort
while (heap.length > 0) {
const [, , node] = heap.shift(); // pop min
curr.next = node;
curr = curr.next;
if (node.next) {
// Insert next node from same list, maintain sorted heap
const entry = [node.next.val, 0, node.next];
let lo = 0, hi = heap.length;
while (lo < hi) {
const mid = (lo + hi) >> 1;
if (heap[mid][0] <= entry[0]) lo = mid + 1; else hi = mid;
}
heap.splice(lo, 0, entry);
}
}
return dummy.next;
}Tradeoff: O(n log k) time — optimal. The heap holds at most k elements, so each push/pop is O(log k). In production JavaScript, implement a real binary heap or use a library. Note this limitation explicitly at DRW.
2. Divide and conquer
Pair up the k lists and merge pairs. Repeat until one list remains. Each round halves the number of lists. Total: O(n log k) with O(log k) recursion depth.
- Time
- O(n log k)
- Space
- O(log k) call stack
function mergeKLists(lists) {
if (lists.length === 0) return null;
function mergeTwoLists(l1, l2) {
const dummy = { next: null };
let curr = dummy;
while (l1 && l2) {
if (l1.val <= l2.val) { curr.next = l1; l1 = l1.next; }
else { curr.next = l2; l2 = l2.next; }
curr = curr.next;
}
curr.next = l1 || l2;
return dummy.next;
}
let interval = 1;
while (interval < lists.length) {
for (let i = 0; i + interval < lists.length; i += interval * 2) {
lists[i] = mergeTwoLists(lists[i], lists[i + interval]);
}
interval *= 2;
}
return lists[0];
}Tradeoff: Same O(n log k) time. No heap overhead — uses only the two-way merge. O(log k) additional space for the iteration bookkeeping. DRW values this approach as an alternative when a heap library is not available.
DRW-specific tips
Frame this as order-book consolidation immediately: 'I have k venues, each publishing sorted price-level updates. I need to merge them into a single consolidated order book in real time.' DRW will ask: 'At 10 million ticks per second across k=10 venues, what is the per-tick latency budget?' O(log k) ≈ 3.3 operations per tick — easily within microsecond budgets. They will also ask about the naive O(nk) pairwise approach and why it is unacceptable.
Common mistakes
- Using the naive approach of merging lists one by one from left to right — O(nk) instead of O(n log k).
- Not handling empty lists in the initial heap population — filter null heads before pushing.
- Simulating the heap with Array.sort() on each iteration — O(n log n) total, not O(n log k).
- Forgetting to advance to node.next after appending a node to the result.
Follow-up questions
An interviewer at DRW may pivot to one of these next:
- Merge k sorted arrays (not linked lists) — same heap approach, but with (value, arrayIndex, elementIndex) triples.
- How would you merge k sorted streams arriving in real time with back-pressure control?
- What is the expected time to fully merge k lists of length n/k each using the divide-and-conquer approach?
Solve it now
Free. No sign-up. Python and JavaScript run instantly in your browser.
FAQ
Why is O(n log k) better than O(n log n)?
When k ≪ n (e.g., k=10 venues, n=10^6 total ticks), log k ≈ 3.3 while log n ≈ 20. The heap approach is roughly 6× faster.
Why does the naive pairwise merge from left to right give O(nk)?
Each of the k-1 merges processes O(n) total elements, but early merges operate on short lists while later ones are long. Amortized cost is O(nk/2) = O(nk).
Is divide and conquer easier to implement than the heap approach in an interview?
Yes — it reuses the two-way merge you likely already wrote, has no heap complexity, and still achieves O(n log k). DRW accepts either.
Practice these live with InterviewChamp.AI
Drill Merge K Sorted Lists and other DRW interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.
Practice these live with InterviewChamp.AI →