23. Merge K Sorted Lists

Q: Why is the heap approach O(N log k) and not O(N log N)?

The heap contains at most k elements at any time. Each push and pop costs O(log k), and you do O(N) total push/pop operations across all N nodes. So total is O(N log k).

Q: Which approach should I present first in a Glean interview?

The min-heap approach — it directly models the production scenario Glean cares about (streaming merge with bounded memory). Mention divide-and-conquer as an alternative that avoids implementing a heap from scratch.

hardAsked at Glean

Merge K Sorted Lists is a cornerstone Glean interview problem — it directly models merging ranked result sets from K index shards into one ordered output stream, a core operation in any distributed search engine.

By Alex Chen, Founder, InterviewChamp.AI · Last verified 2026-05-22

Source citations

Public interview reports confirming this problem appears in Glean loops.

Glassdoor (2026-Q1)— Frequently cited as Glean's signature hard problem — interviewers explicitly connect it to multi-shard result merging in their product.
Blind (2025-12)— Glean SWE candidates list this as the #1 hard problem to prepare — multiple reports of it appearing in the final onsite coding round.

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]

Explanation: All three sorted lists merged into one.

Example 2

Input

lists = []

Output

[]

Explanation: No lists — return null.

Approaches

1. Min-heap (priority queue)

Push the head of each non-null list into a min-heap. Repeatedly extract the minimum node, append it to the merged list, and push the next node from the same list. Repeat until the heap is empty.

Time: O(N log k) where N = total nodes, k = number of lists
Space: O(k) for the heap

// JS has no built-in heap; implement a simple MinHeap
class MinHeap {
  constructor() { this.heap = []; }
  push(node) {
    this.heap.push(node);
    this._bubbleUp(this.heap.length - 1);
  }
  pop() {
    const top = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) { this.heap[0] = last; this._sinkDown(0); }
    return top;
  }
  size() { return this.heap.length; }
  _bubbleUp(i) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[parent].val <= this.heap[i].val) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }
  _sinkDown(i) {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const l = 2*i+1, r = 2*i+2;
      if (l < n && this.heap[l].val < this.heap[smallest].val) smallest = l;
      if (r < n && this.heap[r].val < this.heap[smallest].val) smallest = r;
      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}
function mergeKLists(lists) {
  const heap = new MinHeap();
  for (const head of lists) if (head) heap.push(head);
  const dummy = { val: 0, next: null };
  let tail = dummy;
  while (heap.size() > 0) {
    const node = heap.pop();
    tail.next = node;
    tail = tail.next;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

Tradeoff: O(N log k) time — optimal. The heap always has at most k elements, so log k per extraction. Requires implementing a min-heap in JavaScript — mention this overhead upfront and offer to use a sorted array as a stand-in if implementation time is tight.

2. Divide and conquer (pairwise merge)

Pair up the k lists and merge each pair. Repeat until one list remains. Uses the two-list merge subroutine recursively.

Time: O(N log k)
Space: O(log k) recursion depth

function mergeTwoLists(l1, l2) {
  const dummy = { val: 0, next: null }; let tail = dummy;
  while (l1 && l2) {
    if (l1.val <= l2.val) { tail.next = l1; l1 = l1.next; }
    else { tail.next = l2; l2 = l2.next; }
    tail = tail.next;
  }
  tail.next = l1 || l2;
  return dummy.next;
}
function mergeKLists(lists) {
  if (!lists || lists.length === 0) return null;
  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) complexity. No heap needed — just the two-list merge. Easier to implement correctly in JavaScript. Iterative bottom-up is preferable over recursive to avoid stack depth issues.

Glean-specific tips

State the connection upfront: 'This is exactly what happens when Glean merges ranked results from multiple index shards — each shard returns a sorted list and you merge them efficiently.' Then explain why O(N log k) matters: 'Naive approach is O(Nk) — too slow for k=10,000 shards. The heap-based approach brings it to O(N log k).' Glean interviewers will probe your heap knowledge — be prepared to explain the heap operations. The divide-and-conquer approach is an excellent alternative if implementing a heap from scratch is too slow under pressure.

Common mistakes

Using a naive O(Nk) approach (scan all k heads to find the minimum each time) — works but won't impress for a hard problem.
Not pushing the next node after popping from the heap — the current node's successor must enter the heap.
Forgetting to handle empty lists in the initial heap population — skip null list heads.
In the divide-and-conquer approach, merging out of order — ensure you always merge lists[i] with lists[i + interval], not arbitrary pairs.

Follow-up questions

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

What if each list is a stream (infinite, lazily generated)? How does this change the heap approach?
Merge K Sorted Arrays — same concept but with random-access arrays instead of linked lists.
How would you parallelize this merge across multiple machines in a distributed setting?

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 is the heap approach O(N log k) and not O(N log N)?

The heap contains at most k elements at any time. Each push and pop costs O(log k), and you do O(N) total push/pop operations across all N nodes. So total is O(N log k).

Which approach should I present first in a Glean interview?

The min-heap approach — it directly models the production scenario Glean cares about (streaming merge with bounded memory). Mention divide-and-conquer as an alternative that avoids implementing a heap from scratch.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →