Part 2 · Problems · Two pointers
Merge Sorted Array
#88 · Easy · LeetCode
nums1 has m real values followed by n empty slots. Merge sorted nums2 (n values) into nums1, in place.
nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6] -> [1,2,2,3,5,6]
Ask before coding
- Both sorted ascending?
- In place, no return?
Hint
The empty space is at the end. Which end should you fill from?
Approach
Three pointers from the back: last real value of nums1, last of nums2, last slot. Put the larger one in the slot. Stop when nums2 is used up.
Time O(m + n) Space O(1)
Watch it run
Solution (JavaScript, tested)
function merge(nums1, m, nums2, n) {
// fill from the back so we never overwrite unread values
let i = m - 1,
j = n - 1,
w = m + n - 1;
while (j >= 0) {
if (i >= 0 && nums1[i] > nums2[j]) nums1[w--] = nums1[i--];
else nums1[w--] = nums2[j--];
}
}Traps
- Filling from the front overwrites values you still need.
- Loop on j >= 0. Leftover nums1 values are already in place.
Say out loud: Writing from the front would overwrite data, but the back has free space, so I merge from largest to smallest.