Merge Sorted Array
Easy Merge from the back
- Read
- Understand
- Hints
- Approach
- Solution
- Solved
?The problem
nums1 has m sorted values followed by n empty slots; nums2 has n sorted values. Merge nums2 into nums1 so the result is sorted, in place.
This is a short summary in our own words. Read the full statement and examples on LeetCode: open problem ↗
◎Understanding
Really asking: merge two sorted arrays into the first one, which has empty space at the end.
Why this works: filling from the front would overwrite numbers we still need. The back is empty, so place the largest numbers there first.
Example: nums1 = [1, 2, 3, 0, 0, 0], nums2 = [2, 5, 6]
compare 3 vs 6 → put 6 at end3 vs 5 → put 53 vs 2 → put 32 vs 2 → put 2 (from nums2)result [1, 2, 2, 3, 5, 6]
✦Hints open one at a time
↗Approach
Three pointers: i at the end of nums1's data, j at the end of nums2, k at the very end. Put the larger of nums1[i] and nums2[j] at k and move left. When nums2 runs out, the rest of nums1 is already in place.
</>Solution (Java)
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int i = m - 1, j = n - 1, k = m + n - 1;
while (j >= 0) { // once nums2 is used up we're done
if (i >= 0 && nums1[i] > nums2[j]) nums1[k--] = nums1[i--];
else nums1[k--] = nums2[j--];
}
}
}!Common mistake
Stopping when i runs out — leftover nums2 values still need copying.
- Time: O(m + n).
- Space: O(1).
