Skip to main content

83. Merge k Sorted Lists

hardAsked at Snowflake

Merge k sorted linked lists into one. Snowflake asks this because it's the literal primitive for external sort-merge — when a sort spills to disk and yields k sorted runs, merging them is exactly this problem.

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

Source citations

Public interview reports confirming this problem appears in Snowflake loops.

  • Glassdoor (2026-Q1)— Snowflake execution-engine team's canonical external-sort question.
  • Blind (2025-12)— Recurring at Snowflake SDE-II onsites.

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.length
  • 0 <= k <= 10^4
  • 0 <= lists[i].length <= 500
  • -10^4 <= lists[i][j] <= 10^4
  • lists[i] is sorted in ascending order.
  • The sum of lists[i].length will not exceed 10^4.

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 all into array, sort, rebuild

Walk every list collecting values, sort, build new list.

Time
O(N log N)
Space
O(N)
// outline — works but loses sortedness advantage.

Tradeoff: Ignores the k-way structure.

2. Min-heap of size k (optimal)

Push first node of each list into a min-heap. Pop smallest, append to result, push popped's next.

Time
O(N log k)
Space
O(k)
function mergeKLists(lists) {
  // Simple binary heap
  const heap = [];
  function push(n) { heap.push(n); _up(heap.length - 1); }
  function pop() { const r = heap[0]; const last = heap.pop(); if (heap.length) { heap[0] = last; _down(0); } return r; }
  function _up(i) { while (i > 0) { const p = (i - 1) >>> 1; if (heap[p].val <= heap[i].val) break; [heap[p], heap[i]] = [heap[i], heap[p]]; i = p; } }
  function _down(i) { while (true) { const l = 2*i+1, r = 2*i+2; let s = i; if (l < heap.length && heap[l].val < heap[s].val) s = l; if (r < heap.length && heap[r].val < heap[s].val) s = r; if (s === i) break; [heap[i], heap[s]] = [heap[s], heap[i]]; i = s; } }
  for (const head of lists) if (head) push(head);
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (heap.length) {
    const n = pop();
    tail.next = n;
    tail = n;
    if (n.next) push(n.next);
  }
  tail.next = null;
  return dummy.next;
}

Tradeoff: Each of N elements does log k heap work. Exactly the external sort-merge algorithm Snowflake's executor uses.

Snowflake-specific tips

Snowflake interviewers want the min-heap approach because it's the literal external-merge algorithm. Bonus signal: discuss spill-to-S3 — when a sort exceeds memory, Snowflake writes sorted runs to S3, then merges them via a k-way heap exactly as in this problem.

Common mistakes

  • Trying repeated merge of pairs — that's the divide-and-conquer alternative; same complexity but more bookkeeping.
  • Pushing all N values into the heap at once — that's N log N, not N log k.
  • Forgetting to push the popped node's next — leaves remaining elements unmerged.

Follow-up questions

An interviewer at Snowflake may pivot to one of these next:

  • External merge sort with spill-to-disk.
  • Smallest Range Covering Elements (LC 632).
  • How does Snowflake spill sort runs to S3?

Solve it now

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

Output

Press Run or Cmd+Enter to execute

FAQ

Why a heap of size k?

We only need the smallest current front from each list. A heap of size k holds exactly that, and gives log k per pop/push.

How does this connect to external sort?

When a sort spills, each spill creates a sorted run on disk. The final merge phase reads one block from each run, merges them via a k-way heap exactly like this.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →