Merge two sorted arrays without extra space

Given two integer arrays nums1 and nums2. Both arrays are sorted in non-decreasing order.

Merge both the arrays into a single array sorted in non-decreasing order.

• The final sorted array should be stored inside the array nums1 and it should be done in-place.
• nums1 has a length of m + n, where the first m elements denote the elements of nums1 and rest are 0s.
• nums2 has a length of n.

Optimal Approach#

Because nums1 already has m+n capacity (the extra slots are zeros at the end), we can fill it from the back without needing an auxiliary array. Start two pointers at the last real elements of nums1 (index m-1) and nums2 (index n-1), and a write pointer idx at the very last position of nums1. At each step, place the larger of the two front candidates at idx and advance the corresponding pointer left. When nums2 is fully consumed, all remaining nums1 elements are already in place. This merges in O(m + n) time with O(1) extra space.

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

        int idx = nums1.size()-1;
        while(j >= 0){
            if(i >= 0 && nums1[i] > nums2[j]){
                nums1[idx] = nums1[i--];
            }else{
                nums1[idx] = nums2[j--];
            }
            idx--;
        }

    }
};

Time Complexity: O(n)

Space Complexity: O(1)