23. Merge K Sorted Lists

Q: Why is the time complexity O(n log k) and not O(n log n)?

The heap has at most k elements at any time — one per list. Each of the n total nodes is pushed and popped once, at O(log k) per operation. Since k <= n, log k <= log n, so this is a tighter bound.

Q: Why is divide and conquer also O(n log k)?

There are log(k) rounds of merging. In each round, the total work is O(n) — every node is touched exactly once across all pairwise merges in that round. So total = O(n log k).

hardAsked at Elastic

Merge K sorted linked lists into one sorted list. This is one of the most Elastic-relevant hard problems in existence — merging sorted posting lists from K shards is the exact operation Elasticsearch performs on every multi-shard search query, and the min-heap approach maps one-to-one to the coordinating node's result collection logic.

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

Source citations

Public interview reports confirming this problem appears in Elastic loops.

Glassdoor (2026-Q1)— Merge K Sorted Lists appears in multiple Elastic onsite reports as a hard question that directly tests knowledge of heap-based merging.
Blind (2025-12)— Elastic threads identify this as a domain-relevant hard question — candidates who connect it to shard merging consistently receive higher ratings.

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 to merge.

Example 3

Input

lists = [[]]

Output

[]

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 node, append it to the result, and push the extracted node's next into the heap. Continue until the heap is empty.

Time: O(n log k) where n = total nodes
Space: O(k)

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

Tradeoff: O(n log k) — optimal. Heap size never exceeds k, so each push/pop is O(log k). This is exactly how Elasticsearch's coordinating node merges top-hits from K shards.

2. Divide and conquer — pairwise merge

Repeatedly merge lists in pairs. In each round, the number of lists halves. After log(k) rounds, all lists are merged.

Time: O(n log k)
Space: O(1) per merge

function mergeTwoLists(l1, l2) {
  const dummy = { val: -1, 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;
}
function mergeKLists(lists) {
  if (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) time, O(1) auxiliary space. Good to mention as an alternative that avoids implementing a heap.

Elastic-specific tips

The business context is the key differentiator at Elastic: 'Every Elasticsearch search query executes on each shard independently, returning a sorted local top-K list. The coordinating node merges these K sorted lists using a priority queue — exactly this algorithm.' Elastic interviewers reward this framing significantly. Also discuss the trade-off: the divide-and-conquer approach has better space efficiency for large K, while the heap approach is more natural for streaming inputs where lists arrive one at a time.

Common mistakes

Using a max-heap instead of a min-heap — the minimum value must always be extracted next.
Forgetting to push node.next after extracting a node — each extraction must be followed by inserting the successor.
Not handling null lists in the initial heap population — skip null heads.
Using a naive approach of concatenating all nodes and sorting — O(n log n) instead of O(n log k).

Follow-up questions

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

Merge K Sorted Arrays — same algorithm; use (value, arrayIndex, elementIndex) triples in the heap.
Find Median from Data Stream (LC 295) — uses two heaps to maintain running median.
How does Elasticsearch merge and rank results from 100 shards with different local scores?

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 time complexity O(n log k) and not O(n log n)?

The heap has at most k elements at any time — one per list. Each of the n total nodes is pushed and popped once, at O(log k) per operation. Since k <= n, log k <= log n, so this is a tighter bound.

Why is divide and conquer also O(n log k)?

There are log(k) rounds of merging. In each round, the total work is O(n) — every node is touched exactly once across all pairwise merges in that round. So total = O(n log k).

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →