Merge Many Sorted Chains
HardLinked List
Problem
A log aggregator receives k streams, each already sorted by timestamp. Each stream arrives as an array of integers; build a linked list from each, then combine all of them.
Given lists, an array of sorted integer arrays, return the head of a single linked list containing every value in non-decreasing order.
Example 1
- Input:
- lists = [[1, 4, 5], [1, 3, 4], [2, 6]]
- Output:
- [1, 1, 2, 3, 4, 4, 5, 6]
All eight values, merged in order.
Example 2
- Input:
- lists = []
- Output:
- []
Example 3
- Input:
- lists = [[], [3]]
- Output:
- [3]
Constraints
- 0 ≤ k ≤ 10^4
- 0 ≤ lists[i].length ≤ 500
- Total number of values N ≤ 10^4
- -10^4 ≤ lists[i][j] ≤ 10^4; each lists[i] is sorted.
Hint
Show the first hint
Merging two sorted lists is linear. What does merging them one after another into a running result cost?
Walkthrough
How to approach it
01Clarify before coding
- Can k be 0, or some lists be empty? Yes to both: return an empty list if nothing remains.
- How large can things get? Up to 10^4 lists and 10^4 values in total.
- Must I build linked lists from the arrays? Yes, then merge the lists.
02Brute force
Merge the lists one by one into a running result: result = merge(result, list i).
Cost: O(N · k) in the worst case, because the growing result is walked again for every list; with k = 10^4 lists of one value each that is about 5 · 10^7 steps.
The rest of the walkthrough is in the app
The full walkthrough (key insight, step-by-step, dry run, complexity, edge cases, pitfalls, follow-ups) and solutions in Python and JavaScript are in the app, next to an editor and a terminal that runs your code against the tests.
This problem is part of Pro.