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.
Intuition
Merging from the front would overwrite values we still need. Merging from the back writes into the empty tail of nums1 first, so nothing useful is clobbered. Compare the two largest remaining values and place the bigger at the end.
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
Concatenate-and-sort throws away free information
You could dump nums2 into nums1's empty slots and sort — O((m+n) log(m+n)). But both inputs are already sorted, so sorting redoes work we've been handed for free. A merge should be linear. The obstacle is doing it in place: nums1 is our output, and if we merge from the front we'd overwrite nums1 values we haven't read yet.
Merge from the back into the empty tail
The trick is direction. nums1 has exactly n empty slots at the end — so fill from the back, largest value first. Place three pointers: i at the last real value of nums1, j at the last value of nums2, and k at the very end (the write position). The largest remaining element is always one of nums1[i] or nums2[j]; write the bigger to nums1[k] and step that pointer and k inward. Writing into already-consumed or empty slots means we never clobber unread data.
Drive the loop off nums2
Loop while j >= 0. If nums1 still has values and nums1[i] > nums2[j], place nums1[i]; otherwise place nums2[j]. We stop when nums2 is exhausted, because any nums1 values left are already in their correct final positions — no need to move them. If nums1 was empty to begin with, every nums2 value simply copies in. O(m + n) time, O(1) space.
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.