Java: Merge Sorted Array

Thought Process

To merge two sorted arrays, nums1 and nums2, into nums1 in-place, we can use a three-pointer approach. We start from the end of both arrays and compare the elements. The larger element is placed at the end of nums1, and the corresponding pointer is moved backward. This ensures that we do not overwrite unprocessed elements in nums1. After processing all elements from nums2, remaining elements in nums1 are already correctly placed. 

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
              
        // Given: nums1 has size (m+n)
        int k = nums1.length-1;
      
        // Will be used to iterate on element of nums1 and nums2
        int nums1Idx = m-1;
        int nums2Idx = n-1;
      
        while(nums1Idx>=0 && nums2Idx>=0){
      
            if(nums1[nums1Idx] >= nums2[nums2Idx]){
                nums1[k] = nums1[nums1Idx];
                nums1Idx--;
            }
            else{
                nums1[k] = nums2[nums2Idx];
                nums2Idx--;
            }
            k--;
        }
              
        // For remaining elements of nums2
        while(nums2Idx>=0)
            nums1[k--] = nums2[nums2Idx--];

        // Note: We need not to worry for remaining elements of nums1
        // because if nums1Idx>=0 && nums2Idx=-1, then it means elements 
        // of nums1 are already at their correct position.
    }
}

Code Complexity

Time Complexity: O(m + n)

The algorithm iterates through both arrays once, where m is the size of `nums1` and n is the size of `nums2`. Each comparison and assignment operation is constant time.

Space Complexity: O(1)

The algorithm uses a constant amount of extra space, as it performs the merge in-place without requiring additional storage.

Code copied!