332. Merge K Sorted Chains
A logistics hub receives k delivery manifests, each stored as a chain of package numbers already sorted in non-decreasing order. Some manifests may be empty. The hub needs a single master manifest that contains every package number from every chain, also in non-decreasing order.
Given the array chains, where chains[i] is the head of the i-th chain (or null for an empty chain), merge all chains into one sorted chain and return its head. Only the sorted sequence of values matters. The total number of nodes can reach 100,000 and the number of chains can reach 10,000, so merging the chains into one growing result one after another repeats a lot of work; think about a heap of current heads, or about merging chains in pairs.
Example 1
- Input:
- chains = [[1,4,9],[2,3],[],[5,6,10]]
- Output:
- [1,2,3,4,5,6,9,10]
- Explanation:
The chains 1, 4, 9 and 2, 3 and 5, 6, 10 hold eight values in total (the empty chain adds nothing). Merged in order: [1, 2, 3, 4, 5, 6, 9, 10].
Example 2
- Input:
- chains = [[-5,0,0],[0,7]]
- Output:
- [-5,0,0,0,7]
- Explanation:
Equal numbers from both chains are all kept: [-5, 0, 0, 0, 7].
Constraints
0 ≤ chains.length ≤ 104
0 ≤ chains[i].length; the total number of nodes is at most 105
-105 ≤ node value ≤ 105; every chain is sorted in non-decreasing order
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Time per case
- Python 200 msC++ 50 msJava 100 msJavaScript 100 msTypeScript 100 ms
Expected complexity
- Time
- O(N log k)
- Space
- O(1) extra (O(k) with a heap)