"""
Approach 2 already demonstrates the best possible time
complexity, O(n+m)\mathcal{O}(n + m)O(n+m), but still uses additional space.
This is because the elements of array nums1 have to be stored somwhere so that
they aren't overwritten.

So, what if instead we start to overwrite nums1 from the end, where
there is no information yet?

The algorithm is similar to before, except this time we set p1 to point at index m - 1 of nums1,
p2 to point at index n - 1 of nums2, and p to point at index m + n - 1 of nums1.
This way, it is guaranteed that once we start overwriting the first m values in nums1,
we will have already written each into its new position. In this way, we can eliminate the additional space.

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.
        """

        # Set p1 and p2 to point to the end of their respective arrays.
        p1 = m - 1
        p2 = n - 1

        # And move p backwards through the array, each time writing
        # the smallest value pointed at by p1 or p2.
        for p in range(n + m - 1, -1, -1):
            if p2 < 0:
                break
            if p1 >= 0 and nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 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.
        """

        p = m - 1
        q = n - 1
        r = m + n - 1

        while(p >=0 and q>=0):
            if nums1[p] >= nums2[q]:
                nums1[r] = nums1[p]
                p = p - 1
                r = r - 1
            else:
                nums1[r] = nums2[q]
                q = q - 1
                r = r - 1

        # what if there are corner cases; actually the corner cases won't exist
        while (q >= 0):
            nums1[r] = nums2[q]
            r = r - 1
            q = q - 1