88. Merge Sorted Array
Model: qwen2.5-coder:14b
Topics: Array,Two Pointers
FAANG asked: 1
Acceptance rate: 40.9%
Problem Breakdown
The problem requires merging two sorted integer arrays, nums1 and nums2, into one sorted array. The key points are:
nums1has enough space at the end to accommodate all elements fromnums2.- The number of initialized elements in
nums1ism, and innums2isn. - We need to merge
nums2intonums1in-place.
Inputs:
nums1: A list of integers with lengthm + n, where the lastnelements are zeros.m: An integer representing the number of initialized elements innums1.nums2: A list of integers with lengthn.n: An integer representing the number of elements innums2.
Outputs:
- The merged sorted array, which is stored in
nums1.
Implicit constraints or edge cases:
- If
mis 0, thennums1should be replaced entirely bynums2. - If
nis 0, thennums1remains unchanged. - Both arrays can contain negative numbers and duplicates.
Intuition
A brute-force approach would involve copying the elements of nums1 into a temporary array, then merging both arrays back into nums1. This approach has a time complexity of O(m + n) but requires additional space for the temporary array, which is not ideal since we want to perform the merge in-place.
The key insight is to start from the end of both arrays and work backwards. Since nums1 has extra space at the end, we can use it to store the merged elements without overwriting any unprocessed elements from nums2. This approach allows us to merge the arrays in O(m + n) time complexity with O(1) additional space.
Approach
-
Initialize three pointers:
ipointing to the last element of the initialized part ofnums1(indexm - 1).jpointing to the last element ofnums2(indexn - 1).kpointing to the last position ofnums1(indexm + n - 1).
-
Iterate while both
iandjare non-negative:- Compare the elements at
nums1[i]andnums2[j]. - Place the larger element at
nums1[k]and decrement the corresponding pointer (iorj) andk.
- Compare the elements at
-
If there are remaining elements in
nums2(i.e.,j >= 0), copy them intonums1. This step is necessary because if there are remaining elements innums1, they are already in place. -
The final
nums1will be the merged sorted array.
Complexity Analysis
- Time complexity: O(m + n). We iterate through both arrays once.
- Space complexity: O(1). We use only a constant amount of extra space for pointers.
Solution
def merge(nums1, m, nums2, n):
i, j, k = m - 1, n - 1, m + n - 1
while i >= 0 and j >= 0:
if nums1[i] > nums2[j]:
nums1[k] = nums1[i]
i -= 1
else:
nums1[k] = nums2[j]
j -= 1
k -= 1
# If there are remaining elements in nums2, copy them
while j >= 0:
nums1[k] = nums2[j]
j -= 1
k -= 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]
Edge Cases Handled
- If
mis 0, the entirenums1will be replaced bynums2. - If
nis 0,nums1remains unchanged. - The code handles arrays with negative numbers and duplicates correctly.