83. Merge Sorted Array

Fill nums1 from its last slot backward, always placing the larger of the two current tails. Writing from the end means we never overwrite an nums1 element we still need to compare.

Idea

Merging from the front would overwrite unprocessed nums1 values. The trick is to fill nums1 from the back: the largest remaining element goes into the last free slot. Because that slot is at or beyond both read pointers, we never clobber data we still need.

Algorithm

1. i = m-1 (tail of real nums1), j = n-1 (tail of nums2), k = m+n-1 (last slot).
2. While j >= 0:
   • If i >= 0 and nums1[i] > nums2[j], place nums1[i] at k and decrement i.
   • Else place nums2[j] at k and decrement j.
   • Decrement k.
3. (Any leftover nums1 elements are already in place.)

Worked example: nums1 = [1,2,3,0,0,0] (m=3), nums2 = [2,5,6] (n=3)

• Compare 3 vs 6 → place 6 at index 5.
• 3 vs 5 → place 5 at 4.
• 3 vs 2 → place 3 at 3.
• 2 vs 2 → place 2 (from nums2) at 2.
• 2 vs — (nums2 done after) ... result [1,2,2,3,5,6].

Complexity

• Time: O(m + n).
• Space: O(1) — merged in place.

class Solution {
    public int[] merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k] = nums1[i];
                i--;
            } else {
                nums1[k] = nums2[j];
                j--;
            }
            k--;
        }
        return nums1;
    }
}