[LeetCode] 88. Merge Sorted Array

Problem : https://leetcode.com/problems/merge-sorted-array/

Since nums1 has enough space left to save nums2, which means  len(nums1) > m + n.

We may use the spare spaces from the rare of nums1 to do merging.

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.
        """
        
        i, j = m - 1, n - 1
        p = len(nums1) - 1
        
        while i >= 0 and j >= 0:
            # select the larger number to add to the rear of nums1
            if nums1[i] > nums2[j]:
                nums1[p] = nums1[i]
                i -= 1
            else:
                nums1[p] = nums2[j]
                j -= 1
            
            p -= 1
        
        # add rest number of nums1
        while i >= 0:
            nums1[p] = nums1[i]
            p -= 1
            i -= 1
        
        # add rest number of nums2
        while j >= 0:
            nums1[p] = nums2[j]
            p -= 1
            j -= 1
        
        # move the merged list to the head of nums1
        p += 1
        i = 0
        while i < m + n:
            nums1[i] = nums1[p]
            i += 1
            p += 1
        
        # fill the rest spaces with 0
        while i < len(nums1):
            nums1[i] = 0
            i += 1