88 Merge Sorted Array

Problem Statement

You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.

Instructions

• Merge nums1 and nums2 into a single array sorted in non-decreasing order.

• The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.

For the whole problem statement, please refer here.

Plans

• Use three pointers to compare the elements from the end of both arrays and place the larget element at the end of nums1.

• Since nums1 has enough space to accomodate all elements from both arrays, we can start merging from the end of nums1 to avoid overwriting elements that have not been processed yet.

• After one of the arrays is fully processed, copy any remaining elements from the other array into nums1.

Solution

from typing import List

class Solution:
    def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
        # Initialize pointers from the last elements of nums1, nums2, and the merged array
        p1, p2, p = m - 1, n - 1, m + n - 1

        # Merge elements from the end
        while p1 >= 0 and p2 >= 0:
            # Place the larger element at the end of nums1
            if nums1[p1] > nums2[p2]:
                nums1[p] = nums1[p1]
                p1 -= 1
            else:
                nums1[p] = nums2[p2]
                p2 -= 1
            # Move the pointer to the next element
            p -= 1

        # Copy any remaining elements from nums2 into nums1
        while p2 >= 0:
            nums1[p] = nums2[p2]
            p2 -= 1
            p -= 1

Explanation

1. Initialization

   • We initialize the three pointers p1 for the last valid elements in nums1, p2 for the last elements in nums2, and p for the last position in the merged array nums1.

2. Merging from the End

   • We use while loop to compare the elements from the end of the both arrays (nums1 and nums2). The loop continues as long as there are elements left in both arrays (p1 >= 0 and p2 >= 0).

   • Inside the loop, we compare the elements at nums1[p1] and nums2[p2]. The larger element is placed at the nums1[p], and the corresponding pointer (p1 or p2) is decremented.

3. Handling the Remaining Elements

   • After the main loop, if there are any remaining elements in nums2 (i.e., p2 >= 0), we copy them to the beginning of nums1. This is because all the elements is nums1 have already been processed and moved to their correct positions.

   • We use another while loop to copy the remainng elements from nums2 to nums1. The loop continues as long as there are elements left in nums2 (p2 >= 0).