88. Merge Sorted Array

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Merge nums1 and nums2 into a single array sorted in non-decreasing order. The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

Constraints:

• nums1.length == m + n
• nums2.length == n
• 0 <= m, n <= 200
• 1 <= m + n <= 200
• -109 <= nums1[i], nums2[j] <= 109

Notice that nums1 will take the form nums1 = [A, 0], where A is m elements in the array (nums1), and 0 is n 0s in the array. Therefore, to merge the two lists in-place, we have to track where we can place the merged list and where nums1 starts. To do so, we can merge from largest to smallest, keeping track of the biggest elements of nums1 and nums2 to insert next via their indices, and where the merged list begins.

if len(nums2) == 0: return

# largest number in nums1 is at index m - 1
biggest1 = m - 1
biggest2 = n - 1
largest = m + n - 1

while biggest2 >= 0:
	# we need to check if biggest1 >= 0 in case that n > m, in which case
	# there is nothing to compare once we have inserted n - m elements-we
	# simply insert from nums2.
	# 
	# in the other case, if m > n, then since both lists are sorted, we can
	# simply exit the loop.
	if biggest1 >= 0 and nums1[biggest1] > nums2[biggest2]:
		nums1[largest] = nums1[biggest1]
		biggest1 -= 1
	else:
		nums1[largest] = nums2[biggest2]
		biggest2 -= 1
	
	largest -= 1

Time Complexity

We iterate only through at most $\mathcal{O}(m + n)$ elements, we merge alternately. Since every step in the while loop is constant, and all assignment steps are also constant, the algorithm time complexity is in $\mathcal{O}(m + n)$.

Space Complexity

Notice the only space we use is to store the variables i, j, k. Everything else is given with the input, so our space complexity is $\mathcal{O}(1)$.