merge-sorted-array.py

class Solution:
    # NOTE: extra space: O(m), time: O(n + m)
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        nums1_copy = [None] * m
        for i in range(m):
            nums1_copy[i] = nums1[i]
        
        i1 = 0
        i2 = 0
        while i1 < m or i2 < n:
            if i1 >= m:
                nums1[i1 + i2] = nums2[i2]
                i2 += 1
            elif i2 >= n:
                nums1[i1 + i2] = nums1_copy[i1]
                i1 += 1
            elif nums1_copy[i1] <= nums2[i2]:
                nums1[i1 + i2] = nums1_copy[i1]
                i1 += 1
            else:
                nums1[i1 + i2] = nums2[i2]
                i2 += 1