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^4Both arrays are sorted in non-decreasing order
Complexity
Show Complexity
- Time:
O(n + m) - Space:
O(n + m)
Hints
Show 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
Show PY Solution
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