Merge Sorted Array
Easy· merge· backward fill
Problem
Two sorted arrays are given: nums1 with m real values followed by n empty slots, and nums2 with n values. Merge nums2 into nums1 in place so that nums1 ends up fully sorted.
Examples
Input: nums1 = [1,4,7,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,4,5,6,7]
Input: nums1 = [0], m = 0, nums2 = [3], n = 1
Output: [3]
Constraints
- • nums1.length == m + n
- • 0 <= m, n <= 200
- • Both inputs are sorted in non-decreasing order
Hints & approach
Hint 1
Merging from the front would overwrite values of nums1 you still need.
Hint 2
The empty space is at the back of nums1. Fill it from the back.
Approachtry the hints first
Use three pointers: i = m - 1 (last real value in nums1), j = n - 1 (last in nums2) and w = m + n - 1 (write position). While j >= 0, write the larger of nums1[i] and nums2[j] into nums1[w] and move the corresponding pointers left. Writing from the back never overwrites unread data, and any leftover nums1 values are already in place.
Time O(m + n) · Space O(1)