LeetCode #88: Merge Sorted Array — a classic problem that tests working backwards with arrays.
You're given two sorted arrays nums1 and nums2. Merge nums2 into nums1 in-place. nums1 has extra space at the end (filled with 0s) to hold the merged result.
Example:nums1 = [1, 2, 3, 0, 0, 0], m = 3nums2 = [2, 5, 6], n = 3
→ [1, 2, 2, 3, 5, 6]
The Trick — Fill from the back!
Start at the end of nums1 and fill the largest values first. This avoids overwriting elements we haven't processed yet.
💭 Challenge time! Now implement this yourself using the strategy above. The best way to learn is by doing! ⭐
Why backwards? If we filled from the front, we'd overwrite nums1 elements before using them. By going backwards, we fill the empty space first!
Complexity: Time O(m + n), Space O(1)
def merge(nums1, m, nums2, n):
# Three pointers: end of each array
p1 = m - 1 # Last real element in nums1
p2 = n - 1 # Last element in nums2
write = m + n - 1 # Write position (end of nums1)
while p2 >= 0:
if p1 >= 0 and nums1[p1] > nums2[p2]:
nums1[write] = nums1[p1]
p1 -= 1
else:
nums1[write] = nums2[p2]
p2 -= 1
write -= 1
nums1
[1, 2, 2, 3, 5, 6]
nums2
[1]
nums3
[1]