Combine Two Sorted Array

Description

Given two sorted integer arrays nums1 and nums2, merge them into a single sorted array. Return the merged array.

Example 1:
Input: nums1 = [1, 2, 4], nums2 = [1, 3, 4]
Output: [1, 1, 2, 3, 4, 4]
Explanation: Merge and sort: compare elements, take smaller each time.

Example 2:
Input: nums1 = [1, 2, 3], nums2 = []
Output: [1, 2, 3]
Explanation: nums2 is empty, so result is just nums1.

Example 3:
Input: nums1 = [], nums2 = [1]
Output: [1]
Explanation: nums1 is empty, so result is just nums2.

Constraints

0 <= nums1.length, nums2.length <= 10^4
-10^4 <= nums1[i], nums2[i] <= 10^4
Both arrays are sorted in non-decreasing order

Signature

def solution(nums1: list[int], nums2: list[int]) -> list[int]: ...

Complexity

Time: O(n + m)
Space: O(n + m)

Hints

Pattern: Use two pointers: one for each array
Approach: While both arrays have elements, compare and append smaller. Then append remaining elements from non-empty array.
Complexity: Compare elements at both pointers, take the smaller one each time

Solutions

Python

def solution(arr1, arr2):
    i = 0
    j = 0

    n1 = len(arr1)
    n2 = len(arr2)

    result = []
    while i < n1 and j < n2:
        a = arr1[i]
        b = arr2[j]

        if a < b:
            result.append(a)
            i += 1
        else:
            result.append(b)
            j += 1

    # edge case: arr1 not yet exhausted
    while i < n1:
        a = arr1[i]
        result.append(a)
        i += 1

    # edge case: arr2 not yet exhausted
    while j < n2:
        b = arr2[j]
        result.append(b)
        j += 1

    return result