Leetcode: 88. Merge Sorted Array
Merge Two Sorted Arrays - An In-Place Solution
Given two sorted arrays nums1
and nums2
, you need to merge nums2
into nums1
as one sorted array.
Solution
class Solution {
public:
void merge(vector& nums1, int m, vector& nums2, int n) {
vector nums1copy(nums1.begin(), nums1.begin() + m);
int frontPtr1 = 0, frontPtr2 = 0;
int totalLength = 0;
while (frontPtr1 < m && frontPtr2 < n) {
if (nums1copy[frontPtr1] <= nums2[frontPtr2]) {
nums1[totalLength] = nums1copy[frontPtr1];
frontPtr1++;
} else {
nums1[totalLength] = nums2[frontPtr2];
frontPtr2++;
}
totalLength++;
}
while (frontPtr1 < m) {
nums1[totalLength] = nums1copy[frontPtr1];
frontPtr1++;
totalLength++;
}
while (frontPtr2 < n) {
nums1[totalLength] = nums2[frontPtr2];
frontPtr2++;
totalLength++;
}
}
};
Explanation
The given solution merges two sorted arrays nums1
and nums2
into nums1
as one sorted array. It uses two pointers (frontPtr1
and frontPtr2
) to iterate over the elements of nums1copy
and nums2
and merges them into nums1
.
The solution works as follows:
- Create a copy of the first
m
elements ofnums1
in a new vectornums1copy
. - Initialize two pointers
frontPtr1
andfrontPtr2
to track the current positions innums1copy
andnums2
, respectively. - Initialize a total length variable to keep track of the merged array length.
- Compare the elements at
frontPtr1
innums1copy
andfrontPtr2
innums2
. Select the smaller element and place it in the merged array at the corresponding position. Increment the respective pointers and the total length. - If there are remaining elements in
nums1copy
ornums2
after merging, add them to the end of the merged array.
Complexity Analysis
The time complexity of the solution is O(m+n), where m and n are the lengths of nums1
and nums2
, respectively. The solution traverses both arrays once to merge the elements.
The space complexity is O(m) as we create a copy of nums1
to store the initial elements.
Comments
Post a Comment