Merge Sorted Array
You are given two integer arrays nums1 and nums2, sorted in non-decreasing order, and two integers m and n, representing the number of elements in nums1 and nums2 respectively.
Merge nums1 and nums2 into a single array sorted in non-decreasing order.
The final sorted array should not be returned by the function, but instead be stored inside the array nums1. To accommodate this, nums1 has a length of m + n, where the first m elements denote the elements that should be merged, and the last n elements are set to 0 and should be ignored. nums2 has a length of n.
Example 1:
Input: nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
Output: [1,2,2,3,5,6]
Explanation: The arrays we are merging are [1,2,3] and [2,5,6].
The result of the merge is [1,2,2,3,5,6] with the underlined elements coming from nums1.
Example 2:
Input: nums1 = [1], m = 1, nums2 = [], n = 0
Output: [1]
Explanation: The arrays we are merging are [1] and [].
The result of the merge is [1].
Example 3:
Input: nums1 = [0], m = 0, nums2 = [1], n = 1
Output: [1]
Explanation: The arrays we are merging are [] and [1].
The result of the merge is [1].
Note that because m = 0, there are no elements in nums1. The 0 is only there to ensure the merge result can fit in nums1.
Constraints:
nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-10^9 <= nums1[i], nums2[j] <= 10^9
My Solution
We can solve this problem by creating a separate buffer and merge the two arrays. We then copy the buffer back into nums1. We merge the two arrays with the two pointer technique. One pointer points to the first element of nums1. The second pointer points to the first element of nums2. At each iteration, we add the smaller of the two pointers to our output buffer and then move that pointer forward. Once we have exhausted all the relevant elements of one of the arrays, we add all the elements of the other array to the output buffer. Finally we copy all the elements of the output buffer to the nums1 array.
The time complexity is O(m+n) because we iterate through both of the arrays to merge the two arrays and we have another pass to copy all the elements back to nums1. Space complexity is also O(m+n) because of the space required for the separate output buffer.
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int[] out = new int[m+n];
int i = 0;
int j = 0;
while (i < m && j < n) {
if (nums1[i] <= nums2[j]) {
out[i+j] = nums1[i];
i++;
}
else {
out[i+j] = nums2[j];
j++;
}
}
while (i < m) {
out[i+j] = nums1[i];
i++;
}
while (j < n) {
out[i+j] = nums2[j];
j++;
}
for (i = 0; i < m+n; i++) {
nums1[i] = out[i];
}
}
}