88. Merge Sorted Array

Information

  • Diffculty: Easy

  • Created: 2020-03-10 09:52:00

  • Last Motified: 2020-03-10 09:57:17

  • Tags: Array, Two Pointers

Intuition

Since we need to do a in place merge from nums2 to nums1, we could do it from end to start. So that we don’t need additional space.

Solution

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        index = m + n - 1
        i1, i2 = m - 1, n - 1
        while i2 >= 0:
            if i1 == -1 or nums1[i1] < nums2[i2]:
                nums1[index] = nums2[i2]
                i2 -= 1
            else:
                nums1[index] = nums1[i1]
                i1 -= 1
            index -= 1