Merge Sorted Array
- 2 min read
- LC-Easy
- Two Pointers
3 years ago
Solution
- Trivial solution is to add all elements to a new array by using two pointers, but they specifically want use to use only the
nums1array - To make the code a lot simpler, start filling
nums1from the back instead - You just have to account for the edge case where there are still elements left in
nums2to process- Do a dry run for the case
nums1 = [7, 8, 9, 0, 0, 0] and nums2 = [1, 2, 3]and you'll understand
- Do a dry run for the case
| Time | Space | Explanation | |
|---|---|---|---|
O(n) | O(1) |
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""
i = m + n - 1
m -= 1
n -= 1
while i >= 0 and n >= 0 and m >= 0:
num = None
if nums1[m] >= nums2[n]:
num = nums1[m]
m -= 1
else:
num = nums2[n]
n -= 1
nums1[i] = num
i -= 1
while n >=0 and i >= 0:
nums1[i] = nums2[n]
i -= 1
n -= 1