The original question can be found here.
It’s asking us to merge array nums2 into array nums1. The most straightforward solution is: for each element inside array nums2, we insert into nums1 to find an appropriate position. Once we find an appropriate spot, we need to move all the elements starting from this position to its right position by 1. The time complexity is O(m*n) where m and n are the length for array num1, and num2, respectively.
The follow up question is asking us to come up with a O(m+n) time complexity solution. Since we know that both arrays are sorted, and num1 array has enough spots at right end to hold the data from nums2, so we can start merging 2 arrays from large to small, by putting larger element at right end of nums1. Let’s take a sample input from the question as an example:
nums1: [1, 2, 3, x, x, x]
↑
nums2: [2, 5, 6]
↑First we compare element 3 from nums1 and element 6 from nums2:
nums1: [1, 2, 3, x, x, 6]
↑
nums2: [2, 5, 6]
↑And then we compare element 3 and 5:
nums1: [1, 2, 3, x, 5, 6]
↑
nums2: [2, 5, 6]
↑ Next is 3 and 2:
nums1: [1, 2, 3, 3, 5, 6]
↑
nums2: [2, 5, 6]
↑ Next we compare 2 and 2:
nums1: [1, 2, 2, 3, 5, 6]
↑
nums2: [2, 5, 6]
↑ Since we’re running out of elements from nums2, we stop. But pay attention, if we running out of elements from nums1, we’ll need to copy rest of nums2 array elements to array nums1.
class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
index = m + n - 1
m = m - 1
n = n - 1
while m >= 0 and n >= 0:
if nums2[n] >= nums1[m]:
nums1[index] = nums2[n]
n -= 1
else:
nums1[index] = nums1[m]
m -= 1
index -= 1
while n >= 0:
nums1[index] = nums2[n]
index -= 1
n -= 1Time complexity: O(m + n). Space complexity: O(1)