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