88. Merge Sorted Array¶

Given two sorted array the goal is to merge them

Input
nums1 = [1,2,3,0,0,0], m = 3, 
nums2 = [2,5,6], n = 3

Output
[1,2,2,3,5,6]

the first array has capacity to hold to the merged sorted array.

Intuition¶

• Uses two pointers two track the current position in respective arrays
• Since nums1 is of size \(m+n\) use this extra space to store the merged array.

Approach¶

• Iterate through the arrays from the end and place the larger element in the end of nums1.

Complexity¶

• Time complexity : \(\text{O}(m+n)\)
• Since we iterate over the \(m+n\) array elements only once.
• Space complexity : \(\text{O}(1)\)
• Not using any extra space, apart from the one provided

Code¶

int i  = m-1 , j = n-1; 

// Start filling the merged array from end
for(int k = n+m-1; k >= 0; k--) {
    // We compare if there are elements left in one of the array 
    // if all elements are finished simply put all the remaining 
    // elements
    if(i >= 0 && j >= 0) {
        nums1[k]= nums1[i] > nums2[j] ? nums1[i--] : nums2[j--];
    } else if (i >=0) {
        nums1[k] = nums1[i--];
    } else {
        nums1[k] = nums2[j--];
    }
}

Comments