C++: 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(vector<int>& nums1, int m, vector<int>& nums2, int n)
    {
        int i = m-1; // i for nums1
        int j = n-1; // j for nums2
            
        int k = m+n-1;
        while(i>=0 and j>=0)
        {
            if(nums1[i]>nums2[j])
                nums1[k--] = nums1[i--];
            else // Equals to case yha jayega
                nums1[k--] = nums2[j--];
        }
        
        // For remaining elements of nums2
        while(j>=0)  
            nums1[k--] = nums2[j--]; 
        
        // Note: We need not to worry for remaining elements of nums1
        // because if i>=0 && j=-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!