LC88 Pascal's Triangle II

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.
        """
        # time O((m+n)lg(m+n)) space O(1)
        if not nums1 or not nums2:
            return nums1 + nums2 
        nums1[m:] = nums2[:n]
        nums1.sort()

class Solution:
# main idea:  create new copy of nums1, create 2 pointers for nums1 copy and nums2,  and compare each position
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        """
        Do not return anything, modify nums1 in-place instead.
        """
        # time O(m+n) space O(m)
        if not nums1 or not nums2:
            return nums1 + nums2
        nums1_copy = nums1[:m]
        p1,p2,i = 0,0,0 # i is to track index of nums1
        while p1 < m and p2<n:
            if nums1_copy[p1] <= nums2[p2]:
                nums1[i] = nums1_copy[p1]
                p1 += 1
            else: 
                nums1[i] = nums2[p2]
                p2 +=1
            i += 1
        # if there are still elements to add 
        if p1 < m:
            nums1[i:] = nums1_copy[p1:]
        if p2 < n:
            nums1[i:] = nums2[p2:]
        return nums1

# main idea: back to forward. two pointers for last valid element each nums,  one more pointer to keep track 
# time O(m+n)  space(1)
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.
        """
        # time O(m+n) space O(m)
        p1 = m-1
        p2 = n-1
        p = m+n-1
        while p1>=0 and p2>=0:
            # compare two elements from num1, nums2 and add larger one in nums1
            if nums2[p2] > nums1[p1]:
                nums1[p] = nums2[p2]
                p2 -= 1
            else:
                nums1[p] = nums1[p1]
                p1 -= 1
            p -= 1
        if p2 >=0 :  # if nums2 is not empty 
            nums1[:p+1] = nums2[:p2+1]  # here be careful the range