Merge Two Sorted Arrays

Merge Two Sorted Arrays

You are given two integer arrays, nums1 and nums2, both sorted in non-decreasing order.

Write a function merge_sorted_arrays(nums1: list[int], nums2: list[int]) -> list[int] that combines all elements from both arrays into a single, newly allocated array sorted in non-decreasing order. Every duplicate element from both input arrays must be preserved in the output.

You must not mutate either nums1 or nums2.

Function Signature

def merge_sorted_arrays(nums1: list[int], nums2: list[int]) -> list[int]:
    pass

Constraints

• 0 <= len(nums1), len(nums2) <= 10^6
• -10^9 <= nums1[i], nums2[j] <= 10^9
• nums1 and nums2 are sorted in non-decreasing order.
• Expected time complexity: O(m + n) where m = len(nums1) and n = len(nums2).
• Expected auxiliary space complexity: O(1) extra space beyond the memory required for the output array.

Examples

Example 1:

Input: nums1 = [1, 2, 4, 7], nums2 = [2, 3, 5, 7, 8]
Output: [1, 2, 2, 3, 4, 5, 7, 7, 8]
Explanation: Elements 2 and 7 appear in both arrays and are both included twice in sorted order.

Example 2:

Input: nums1 = [], nums2 = [0, 5]
Output: [0, 5]
Explanation: An empty input array returns a copy of the non-empty array.

Edge Cases to Consider

• One or both input arrays are empty.
• All elements of one array are strictly smaller or larger than all elements of the other.
• Multiple identical elements exist across both arrays.
• Negative numbers and zero.