88. Merge Sorted Array

Solution 1: Two Pointers

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        idxI = m - 1
        idxJ = n - 1
        idxMerged = m + n - 1
        
        # Place the largest elmt to the right place (From end)
        while idxI >= 0 and idxJ >= 0:
            if nums2[idxJ] > nums1[idxI]:
                nums1[idxMerged] = nums2[idxJ]
                idxJ -= 1
            else:
                nums1[idxMerged] = nums1[idxI]
                idxI -= 1
            idxMerged -= 1
        
        # Deal with the rest of array, we don't need to consider idxI since it has been already in the right slot
        # while idxI >= 0:
        #    nums1[idxMerged] = nums1[idxI]
        #    idxI -= 1
        #    idxMerged -= 1
        while idxJ >= 0:
            nums1[idxMerged] = nums2[idxJ]
            idxJ -= 1
            idxMerged -= 1
            
        return nums1

Time Complexity: O(m + n)
Space Complexity: O(1)

Solution 1 - 2: Two Pointers

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        while n > 0:
            if m <= 0 or nums2[n - 1] >= nums1[m - 1]:
                nums1[m + n - 1] = nums2[n - 1]
                n -= 1
            else:
                nums1[m + n - 1] = nums1[m - 1]
                m -= 1
        return nums1

Time Complexity: O(m + n)
Space Complexity: O(1)

Reference

https://leetcode.com/problems/merge-sorted-array/discuss/29522/This-is-my-AC-code-may-help-you
https://leetcode.com/problems/merge-sorted-array/discuss/29503/Beautiful-Python-Solution

Follow-ups

21. Merge Two Sorted Lists
22. Interval List Intersections