Merge Into the Reserved Tail
EasyArrays & Hashing
Problem
Two warehouses keep sorted price lists. The first list lives in primary, whose first m slots hold its prices in non-decreasing order and whose last n slots are reserved placeholders set to 0. The second list is secondary, with exactly n prices, also sorted.
Merge secondary into primary in place so that primary holds all m + n prices in non-decreasing order. The function returns nothing.
Example 1
- Input:
- primary = [1, 4, 7, 0, 0, 0], m = 3, secondary = [2, 5, 6], n = 3
- Output:
- [1, 2, 4, 5, 6, 7]
The three placeholders are replaced and the whole array is sorted.
Example 2
- Input:
- primary = [3, 0], m = 1, secondary = [1], n = 1
- Output:
- [1, 3]
Example 3
- Input:
- primary = [5, 6], m = 2, secondary = [], n = 0
- Output:
- [5, 6]
Constraints
- primary.length = m + n
- 0 ≤ m, n ≤ 200
- 1 ≤ m + n ≤ 200
- -10^9 ≤ values ≤ 10^9
Hint
Show the first hint
Merging from the front would overwrite primary values you still need. Where is the free space?
Walkthrough
How to approach it
01Clarify before coding
- Are the placeholder zeros real values? No, they are free slots; only the first m entries of primary count.
- Can either list be empty? Yes, m or n can be 0.
- Do ties need any particular order? No, equal values are indistinguishable in the result.
02Brute force
Copy secondary into the placeholder slots and sort the whole array.
Cost: O((m + n) log(m + n)) time; it ignores that both halves 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.
This problem is part of Pro.