Merge Sorted Array

How it works

This is a cleaner version of the previous approach. We observe that once all elements from nums2 are placed, the remaining elements of nums1 are already in their correct positions. So we only need to loop while j >= 0. This simplifies the logic and removes the need for a separate cleanup loop.

Steps

1. Initialize pointers i = m - 1, j = n - 1, and last = m + n - 1.
2. While j >= 0:
   • If i >= 0 and nums1[i] > nums2[j], place nums1[i] at nums1[last] and decrement i.
   • Otherwise, place nums2[j] at nums1[last] and decrement j.
   • Decrement last.

Complexity

• Time complexity: O(m + n)
• Space complexity: O(1) extra space.

Where m and n represent the number of elements in the arrays nums1 and nums2, respectively.

Things to watch for

Merging From the Front Instead of the Back

When merging in place, starting from the front of nums1 overwrites elements that have not yet been processed. This destroys data you still need. Always merge from the back of nums1 where there is empty space, placing the largest elements first.

Forgetting to Copy Remaining Elements From nums2

After the main merge loop, if there are remaining elements in nums2, they must be copied to nums1. Elements remaining in nums1 are already in their correct positions, but leftover nums2 elements need explicit placement. Missing this step leaves the result incomplete.

class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        last = m + n - 1
        i, j = m - 1, n - 1

        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[last] = nums1[i]
                i -= 1
            else:
                nums1[last] = nums2[j]
                j -= 1

            last -= 1

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int last = m + n - 1;
        int i = m - 1, j = n - 1;

        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[last--] = nums1[i--];
            } else {
                nums1[last--] = nums2[j--];
            }
        }
    }
};