Merge Sorted Array
LeetCode #88 · Easy · Arrays · C++ solution with worked-out approach and complexity analysis.
Approach
Two Pointers (Reverse)
Strategy
- 1Use three pointers:
- 2Iterate backwards from the end of nums1.
- 3Compare elements at `nums1[m]` and `nums2[n]`.
- 4Place the larger element at `nums1[i]` and decrement the corresponding
- 5If one array is exhausted, copy the remaining elements from the other
Time
O(m + n)
Space
O(1)
Problem description(from LeetCode)
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.
Examples
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]
- Note:
- 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. Input: nums1 = [1], m = 1, nums2 = [], n = 0 Output: [1] Input: nums1 = [0], m = 0, nums2 = [1], n = 1 Output: [1]
Constraints
- •nums1.length == m + n
- •nums2.length == n
- •0 <= m, n <= 200
- •1 <= m + n <= 200
- •-10^9 <= nums1[i], nums2[j] <= 10^9
C++ Solution
solution.cpp
class Solution {
public:
void merge(vector<int> &nums1, int m, vector<int> &nums2, int n) {
int i = m + n - 1;
m--;
n--;
while (i >= 0) {
if (m < 0) {
nums1[i--] = nums2[n--];
} else if (n < 0) {
nums1[i--] = nums1[m--];
} else if (nums1[m] >= nums2[n]) {
nums1[i--] = nums1[m--];
} else {
nums1[i--] = nums2[n--];
}
}
}
};