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--];
	}
}