Merge Sorted Array easy

Problem Statement

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

The number of elements initialized in nums1 and nums2 are m and n respectively. You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2.

Example 1

Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3 Output: [1,2,2,3,5,6] Explanation: The merged array is [1,2,2,3,5,6]

Example 2

Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Explanation: The merged array is [1]

Steps

1. Initialize Pointers: Use three pointers: p1 to point to the end of nums1 (initially m-1), p2 to point to the end of nums2 (initially n-1), and p to point to the end of the merged array in nums1 (initially m+n-1).

2. Compare and Place: Compare the elements at nums1[p1] and nums2[p2]. The larger element is placed at nums1[p]. Decrement the pointer of the larger element.

3. Handle Remaining Elements: After one of the pointers (p1 or p2) reaches its beginning, copy the remaining elements from the other array to nums1.

Explanation

The algorithm works by iterating from the end of both arrays. This avoids the need to shift elements repeatedly, making it more efficient. By comparing the last elements of both arrays and placing the larger one at the end of nums1, we build the sorted merged array from right to left. This avoids the need for extra space to store the merged array temporarily.

Code

def merge(nums1, m, nums2, n):
    """
    Merges two sorted arrays into nums1.

    Args:
        nums1: The first sorted array.
        m: The number of elements in nums1.
        nums2: The second sorted array.
        n: The number of elements in nums2.
    """
    p1 = m - 1  # Pointer for nums1
    p2 = n - 1  # Pointer for nums2
    p = m + n - 1  # Pointer for the merged array in nums1

    while p1 >= 0 and p2 >= 0:
        if nums1[p1] > nums2[p2]:
            nums1[p] = nums1[p1]
            p1 -= 1
        else:
            nums1[p] = nums2[p2]
            p2 -= 1
        p -= 1

    # Copy remaining elements from nums2 if any
    nums1[:p2 + 1] = nums2[:p2 + 1]


# Example usage
nums1 = [1, 2, 3, 0, 0, 0]
m = 3
nums2 = [2, 5, 6]
n = 3
merge(nums1, m, nums2, n)
print(nums1)  # Output: [1, 2, 2, 3, 5, 6]

nums1 = [1]
m = 1
nums2 = []
n = 0
merge(nums1, m, nums2, n)
print(nums1)  # Output: [1]

Complexity

• Time Complexity: O(m + n) - We iterate through both arrays once.
• Space Complexity: O(1) - We use a constant amount of extra space (the pointers).