K-Way Merge with a Min-Heap

Reported in interviews at American Express Citadel LinkedIn

Problem statement

You are given $k$ sorted lists with a combined total of $n$ elements. Merge them into a single sorted list.

Constraints:

  • $1 \le k \le 10^4$
  • $0 \le n \le 10^6$
  • Each list is sorted in non-decreasing order
  • Some lists may be empty
  • Elements may have equal keys

Requirements:

  • Achieve $O(n \log k)$ time and $O(k)$ extra space using a min-heap.
  • Handle empty lists gracefully.
  • Discuss how to maintain stability (preserve the relative order of equal keys from different lists).
  • Describe how an iterator-based interface would work if the merged output is consumed lazily.

Example 1:

  • Input: [[1, 4, 7], [2, 5, 8], [3, 6, 9]]
  • Output: [1, 2, 3, 4, 5, 6, 7, 8, 9]

Example 2:

  • Input: [[1, 3, 3], [], [2, 3]]
  • Output: [1, 2, 3, 3, 3]
Show hint

Among all the elements not yet output, where can the next smallest one possibly be sitting?

Relevant roles: ML Engineer, Forward Deployed Engineer and AI Engineer.

Related free problems