Solution Explanation: Merge Sorted Array

The problem asks to merge two sorted arrays, nums1 and nums2, into nums1 in a sorted manner. nums1 initially contains m elements, followed by n zeros to accommodate the elements from nums2.

Approach: Two Pointers (Optimal)

The most efficient approach uses a two-pointer technique. This avoids the need for extra space and achieves linear time complexity.

1. Initialization: We start with three pointers:

   • k: Points to the end of nums1 (index m + n - 1). This is where we'll place the merged elements.
   • i: Points to the end of the valid portion of nums1 (index m - 1).
   • j: Points to the end of nums2 (index n - 1).

2. Iteration: We iterate while j (pointer for nums2) is within the bounds of nums2. In each iteration:

   • We compare nums1[i] and nums2[j].
   • The larger element is placed at nums1[k].
   • The pointer corresponding to the larger element is decremented (i or j).
   • k is always decremented to move to the next position in nums1.

3. Handling Remaining Elements: After the loop, if i is still within nums1's valid bounds, then it implies that there are some elements in nums1 that haven't been considered. However, since nums1 is already sorted, these elements are already in the correct position. If any elements remain in nums2, they are already smaller than all elements in the remaining portion of nums1. Therefore, no further action is needed.

Time and Space Complexity

• Time Complexity: O(m + n). The algorithm iterates through both arrays once.
• Space Complexity: O(1). The algorithm operates in-place; no extra space is used proportional to the input size.

Code Examples (with detailed comments)

Python:

class Solution:
    def merge(self, nums1: list[int], m: int, nums2: list[int], n: int) -> None:
        """
        Merges nums2 into nums1 in-place using a two-pointer approach.
        """
        # Pointers for nums1, nums2, and the merged array
        k = m + n - 1  # End of nums1 (merged array)
        i = m - 1      # End of valid portion of nums1
        j = n - 1      # End of nums2
 
        # Iterate until we've processed all elements in nums2
        while j >= 0:
            if i >= 0 and nums1[i] > nums2[j]:
                nums1[k] = nums1[i]  # Place larger element from nums1
                i -= 1               # Move pointer for nums1
            else:
                nums1[k] = nums2[j]  # Place larger element from nums2
                j -= 1               # Move pointer for nums2
            k -= 1                   # Move pointer for merged array

Java:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = m + n - 1; // index of the last element in nums1 (merged array)
        int i = m - 1;     // index of the last element in the valid portion of nums1
        int j = n - 1;     // index of the last element in nums2
 
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            } else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

The code in other languages (C++, Go, TypeScript, Rust, Javascript, PHP) follows a very similar structure, employing the same two-pointer approach. The core logic remains consistent across all implementations.