88. Merge Sorted Array
You receive two integer arrays that are each sorted in non-decreasing order: nums1 and nums2, along with their element counts m and n. The twist is capacity: nums1 is allocated with length m + n — its first m slots hold real values and its last n slots are placeholder zeros reserved for the merge.
Fold nums2 into nums1 in place, so that when your function returns, nums1 holds all m + n values in non-decreasing order. Return nothing — the result must live in nums1 itself.
Example 1:
Input: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
Output: nums1 becomes [1, 2, 2, 3, 5, 6]
Explanation: The six values interleave into one sorted run. Duplicates (the two 2s) both survive — a merge keeps every element.
Example 2:
Input: nums1 = [4, 0, 0], m = 1, nums2 = [-1, 9], n = 2
Output: nums1 becomes [-1, 4, 9]
Explanation: -1 slides in before 4 and 9 lands after it; nums1's reserved tail slots absorb the extra elements.
Constraints:
- 0 ≤ m, n ≤ 200
- 1 ≤ m + n ≤ 400
- -10⁹ ≤ value ≤ 10⁹
- nums1's first m values and nums2 are each sorted in non-decreasing order
- nums1 has length m + n; its last n slots are placeholders
Hints:
Merging front-to-back forces you to shift nums1's remaining values right every time a nums2 value is smaller. Where in nums1 is there guaranteed free space to write into?
Fill from the back. The largest of the two array tails belongs at index m + n − 1, and every write lands on a slot whose value is either a placeholder or has already been moved — so nothing real is ever overwritten. When nums2's pointer is exhausted you can stop: leftover nums1 values are already in place.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: nums1 = [1, 2, 3, 0, 0, 0], m = 3, nums2 = [2, 5, 6], n = 3
Expected output: [1, 2, 2, 3, 5, 6]