### 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 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.

## Comments

## Post a Comment