K-Way Merge with a Min-Heap
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
- Distributed Merge SortMedium