Skip to main content

25. Merge k Sorted Lists

hardAsked at Monzo

Merge k sorted ledger streams (one per shard) into a single time-ordered transaction feed.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

You are given an array of k linked-lists, each linked-list is sorted in ascending order. Merge all the linked-lists into one sorted linked-list and return it. The total number of nodes can be large; aim for O(N log k).

Constraints

  • k == lists.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500

Examples

Example 1

Input
lists = [[1,4,5],[1,3,4],[2,6]]
Output
[1,1,2,3,4,4,5,6]

Example 2

Input
lists = []
Output
[]

Approaches

1. Collect and sort

Push every value into an array, sort it, then rebuild a linked list.

Time
O(N log N)
Space
O(N)
const vals = [];
for (const head of lists) { let cur = head; while (cur) { vals.push(cur.val); cur = cur.next; } }
vals.sort((a, b) => a - b);
const dummy = { next: null }; let tail = dummy;
for (const v of vals) { tail.next = { val: v, next: null }; tail = tail.next; }
return dummy.next;

Tradeoff:

2. Min-heap of list heads

Push the head of each list into a min-heap, then repeatedly pop the smallest and push its successor. Total work is N log k.

Time
O(N log k)
Space
O(k)
function mergeKLists(lists) {
  const h = [];
  const up = i => { while (i > 0) { const p = (i-1) >> 1; if (h[p].val <= h[i].val) break; [h[p], h[i]] = [h[i], h[p]]; i = p; } };
  const down = i => { const n = h.length; while (true) { const l = 2*i+1, r = 2*i+2; let s = i; if (l < n && h[l].val < h[s].val) s = l; if (r < n && h[r].val < h[s].val) s = r; if (s === i) break; [h[s], h[i]] = [h[i], h[s]]; i = s; } };
  for (const node of lists) if (node) { h.push(node); up(h.length - 1); }
  const dummy = { next: null }; let tail = dummy;
  while (h.length) {
    const top = h[0];
    if (top.next) { h[0] = top.next; down(0); } else { h[0] = h.pop(); if (h.length) down(0); }
    tail.next = top; tail = top;
  }
  tail.next = null;
  return dummy.next;
}

Tradeoff:

Monzo-specific tips

Monzo specifically asks for the heap version because their faster-payments pipeline merges per-shard ledger streams in production.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Practice these live with InterviewChamp.AI

Drill Merge k Sorted Lists and other Monzo interview questions under real-loop conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →