Skip to main content

23. Merge K Sorted Lists

hardAsked at Cohere

Merge k sorted linked lists into one sorted list. Cohere asks this because k-way merge is the core algorithm for combining ranked results from multiple retrieval shards in a distributed RAG system — minimising latency while maintaining global ordering.

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

Source citations

Public interview reports confirming this problem appears in Cohere loops.

  • Glassdoor (2026-Q1)— Cohere SWE and MLE onsite reports list Merge K Sorted Lists as a hard problem with a retrieval-systems framing.
  • Blind (2025-12)— Cohere Blind threads recommend practising this as a high-signal hard problem combining heaps and linked lists.

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 lists merged in sorted order.

Example 2

Input
lists = []
Output
[]

Explanation: Empty input.

Example 3

Input
lists = [[]]
Output
[]

Explanation: Single empty list.

Approaches

1. Min-heap

Push the head node of each non-null list into a min-heap keyed by node value. Repeatedly extract the minimum, append it to the result, and push its next node into the heap.

Time
O(N log k) where N = total nodes
Space
O(k)
// Min-heap implementation (JS has no built-in heap)
class MinHeap {
  constructor() { this.heap = []; }
  push(node) {
    this.heap.push(node);
    this._bubbleUp(this.heap.length - 1);
  }
  pop() {
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length) { this.heap[0] = last; this._siftDown(0); }
    return min;
  }
  _bubbleUp(i) {
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.heap[p].val <= this.heap[i].val) break;
      [this.heap[p], this.heap[i]] = [this.heap[i], this.heap[p]];
      i = p;
    }
  }
  _siftDown(i) {
    const n = this.heap.length;
    while (true) {
      let min = i, l = 2*i+1, r = 2*i+2;
      if (l < n && this.heap[l].val < this.heap[min].val) min = l;
      if (r < n && this.heap[r].val < this.heap[min].val) min = r;
      if (min === i) break;
      [this.heap[min], this.heap[i]] = [this.heap[i], this.heap[min]];
      i = min;
    }
  }
  get size() { return this.heap.length; }
}
function mergeKLists(lists) {
  const heap = new MinHeap();
  for (const head of lists) if (head) heap.push(head);
  const dummy = { val: 0, next: null };
  let curr = dummy;
  while (heap.size) {
    const node = heap.pop();
    curr.next = node;
    curr = curr.next;
    if (node.next) heap.push(node.next);
  }
  return dummy.next;
}

Tradeoff: O(N log k) — optimal. Heap always holds at most k nodes. This is the production-grade approach for merging k retrieval shards.

2. Divide and conquer (pairwise merge)

Repeatedly pair up lists and merge each pair using the two-list merge subroutine. Each round halves the number of lists in O(log k) rounds, each round processing all N nodes.

Time
O(N log k)
Space
O(log k) call stack
function mergeTwo(l1, l2) {
  const dummy = { val: 0, 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) return null;
  let interval = 1;
  while (interval < lists.length) {
    for (let i = 0; i + interval < lists.length; i += interval * 2) {
      lists[i] = mergeTwo(lists[i], lists[i + interval]);
    }
    interval *= 2;
  }
  return lists[0];
}

Tradeoff: Same O(N log k) complexity, no heap required. Easier to implement correctly in JS since there is no built-in priority queue. Discuss both and let the interviewer choose.

Cohere-specific tips

Cohere retrieval systems merge candidate lists from multiple embedding index shards. Frame your answer: 'Each retrieval shard returns its top-k chunks sorted by similarity score — merging k sorted lists is exactly the algorithm that produces the globally-ranked candidate set for reranking.' Mention that the heap approach mirrors real distributed merge systems (e.g., top-k aggregation in search engines). Be ready to write the MinHeap from scratch in JS since there is no built-in.

Common mistakes

  • Not pushing the next node after extracting from the heap — the heap must be fed continuously.
  • Initialising the heap with all N nodes instead of just the k heads — defeats the O(k) space advantage.
  • In the divide-and-conquer approach, incorrect interval doubling — use i += interval * 2 to advance past processed pairs.
  • Forgetting to handle empty lists and null heads — guard every heap.push with a null check.

Follow-up questions

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

  • Find the K-th Smallest Element Among K Sorted Arrays — heap with array-index bookkeeping.
  • Smallest Range Covering Elements from K Lists (LC 632) — sliding window of heap min/max.
  • How would you merge k sorted document-chunk streams in a distributed retrieval system?

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

The heap holds at most k elements at any time. Each of the N insertions and extractions costs O(log k), giving O(N log k) total — much better than O(N log N) sort-all.

Which approach is easier to implement under time pressure?

Divide-and-conquer, because it only requires the two-list merge subroutine. The heap approach requires a correct MinHeap implementation in JS, which adds ~25 lines of code.

How would you parallelise this?

The divide-and-conquer approach is naturally parallel: each pair of lists can be merged independently in each round. Distribute the pairs across workers and reduce in O(log k) rounds — similar to a parallel merge sort.

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →