Merge Sorted Array
Merge sorted nums2 (length n) into sorted nums1 (length m, with n empty slots at the end) so nums1 becomes one sorted array — in place.
- nums1.length == m + n
- nums2.length == n
- 0 <= m, n <= 200
- 1 <= m + n <= 200
- -10⁹ <= nums1[i], nums2[j] <= 10⁹
Intuition
Merge sorted array merges nums2 into nums1, which already has exactly enough trailing space. The merge itself is standard; the in-place requirement is what shapes the solution.
Merging forwards from the start fails. Writing into nums1[0] overwrites a value that has not been merged yet, so a forward merge needs a temporary copy and O(m) extra space.
The fix is to reverse the direction:
- Fill from the back, comparing the largest remaining elements and writing to the last unfilled position — the space being written is always already consumed.
That works because the trailing region of nums1 is empty by construction. Every write lands either in that empty space or on a slot whose value has already been placed further right.
So three pointers run backwards: one at the last real element of nums1, one at the end of nums2, and one at the very end of nums1. At each step the larger of the two candidates is written and its pointer moves left.
When the loop ends, any remaining elements in nums2 must still be copied. Remaining elements in nums1 need no action — they are already in place, which is a useful asymmetry to notice.
The common bug is looping only while both pointers are valid and then forgetting the nums2 remainder. Leftover nums2 values are smaller than everything placed, so they belong at the front and are genuinely missing without that step.
The merge is O(m + n) time and O(1) space, touching each element exactly once.
Fill from the back. nums1 has exactly m + n slots and its tail is free, so writing the largest element first means you never overwrite a value you still need. Whenever an in-place merge has spare room at one end, filling from that end removes the need for a temporary buffer.
Approach
Before reading on: price up what sorting first costs here, then ask what makes it safe to discard one end without checking it against everything. Aim for O(m + n) time and O(1) space.
See why forwards fails
Writing to nums1[0] overwrites a value not yet merged, so a forward merge needs a temporary copy and O(m) extra space.
Fill from the back
Compare the largest remaining elements and write to the last unfilled slot. The space being written is always already consumed, so nothing is clobbered.
Run three pointers backwards
Place one at nums1's last real element, one at nums2's end, and one at nums1's very end. Write the larger candidate and move its pointer left.
Copy the nums2 remainder
Any leftover nums2 elements must still be copied. They are smaller than everything placed and belong at the front — forgetting them is the standard bug.
Leave the nums1 remainder alone
Remaining nums1 elements are already in their correct positions and need no action. This asymmetry is what makes the loop condition simpler than it looks.
Cost of the merge
Each element is written exactly once, giving O(m + n) time and O(1) space — the in-place requirement met without a temporary array.
Solution & live demo
Common pitfalls
Merging forward from index 0
i = j = k = 0
while ...:
nums1[k] = min(nums1[i], nums2[j])i, j, k = m - 1, n - 1, m + n - 1
Writing to the front overwrites unread elements of nums1, so the values you still need to compare are destroyed. The tail is empty, so writing backwards is always safe.
Looping while both i and j are valid
while i >= 0 and j >= 0:
while j >= 0:
If nums1 runs out first, the remaining nums2 values still need copying. Driving the loop on j alone handles that automatically; leftover nums1 values need no work because they are already in their correct positions.
Using >= in the comparison and reading nums1 out of range
if nums1[i] > nums2[j]:
if i >= 0 and nums1[i] > nums2[j]:
Once i drops below zero, nums1[i] silently wraps to the end of the array in Python and throws in C++/Java. The bounds check must be part of the same condition.
Edge cases
The i >= 0 guard fails immediately, so every nums2 value is copied straight in.
The loop condition j >= 0 is false at once; nums1 is already complete.
They are placed last only after nums1's values shift to the high end — order stays correct.