### Leetcode: 88. Merge Sorted Array

Merge Two Sorted Arrays - An In-Place Solution

# 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 of `nums1` in a new vector `nums1copy`.
• Initialize two pointers `frontPtr1` and `frontPtr2` to track the current positions in `nums1copy` and `nums2`, respectively.
• Initialize a total length variable to keep track of the merged array length.
• Compare the elements at `frontPtr1` in `nums1copy` and `frontPtr2` in `nums2`. 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` or `nums2` 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.