Merge Two Sorted Feeds
EasyTwo PointersFree
Problem
Two sensors each produce a list of timestamps already sorted in non-decreasing order: a and b. A dashboard needs one combined list, also in non-decreasing order, that contains every timestamp from both (duplicates included).
Return the merged list in O(len(a) + len(b)) time.
Example 1
- Input:
- a = [1, 4, 9], b = [2, 3, 10, 12]
- Output:
- [1, 2, 3, 4, 9, 10, 12]
At each step take the smaller front value of the two lists.
Example 2
- Input:
- a = [], b = [5, 6]
- Output:
- [5, 6]
Constraints
- 0 ≤ a.length, b.length ≤ 10^5
- -10^9 ≤ a[i], b[i] ≤ 10^9
- a and b are sorted in non-decreasing order
Hint
Show the first hint
The smallest element of the result must be the front of a or the front of b.
Walkthrough
How to approach it
01Clarify before coding
- Should duplicates be kept? Yes, every timestamp appears in the output as many times as in the inputs.
- Can either list be empty? Yes, then the answer is a copy of the other list.
- May I modify the inputs? Not needed: return a new list.
02Brute force
Concatenate the two lists and sort the result.
Cost: O((n + m) log(n + m)) time: it throws away the fact that both inputs are already sorted.
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.