Merge Sorted Array

Problem Id: 88 Difficulty: Easy Tag: Array Tag: 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