You are given two integer arrays, nums1 and nums2, both sorted in non-decreasing order. Your task is to merge these two arrays into a single new sorted array.

Solution

The most straightforward approach involves using two pointers.

  • Initialize two pointers, p1 for nums1 and p2 for nums2, both starting at index 0.
  • Create an empty result array to store the merged elements.
  • While both p1 is within nums1 bounds and p2 is within nums2 bounds:
    • Compare nums1[p1] and nums2[p2].
    • Append the smaller element to result and increment its corresponding pointer.
  • After the loop, one of the arrays might still have remaining elements. Append all remaining elements from nums1 (if any) and nums2 (if any) to result.
  • Return the result array.
def merge_sorted_arrays(nums1: list[int], nums2: list[int]) -> list[int]:
    p1 = 0
    p2 = 0
    result = []

    while p1 < len(nums1) and p2 < len(nums2):
        if nums1[p1] < nums2[p2]:
            result.append(nums1[p1])
            p1 += 1
        else:
            result.append(nums2[p2])
            p2 += 1

    # Append remaining elements from nums1, if any
    while p1 < len(nums1):
        result.append(nums1[p1])
        p1 += 1

    # Append remaining elements from nums2, if any
    while p2 < len(nums2):
        result.append(nums2[p2])
        p2 += 1

    return result