# LeetCode 88. Merge Sorted Array

## Description

https://leetcode.com/problems/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 = , m = 1, nums2 = [], n = 0
Output: 
Explanation: The arrays we are merging are  and [].
The result of the merge is .
```

Example 3:

```Input: nums1 = , m = 0, nums2 = , n = 1
Output: 
Explanation: The arrays we are merging are [] and .
The result of the merge is .
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`
• `-109 <= nums1[i], nums2[j] <= 109`

Follow up: Can you come up with an algorithm that runs in `O(m + n)` time?

## Explanation

Create a copy of nums1 to keep the original values. Then set one pointer at the beginning of nums1, another pointer at the beginning of nums2, and push the smallest value in the nums1 array at each step.

## Python Solution

``````class Solution:
def merge(self, nums1: List[int], m: int, nums2: List[int], n: int) -> None:
"""
Do not return anything, modify nums1 in-place instead.
"""

nums1_copy = list(nums1)

i = 0
j = 0

index = 0
while i < m and j < n:
if nums1_copy[i] < nums2[j]:
nums1[index] = nums1_copy[i]
i += 1
else:
nums1[index] = nums2[j]
j += 1
index += 1

while i < m:
nums1[index] = nums1_copy[i]
i += 1
index += 1

while j < n:
nums1[index] = nums2[j]
j += 1
index += 1``````
• Time complexity: O(m + n).
• Space complexity: O(m + n).

## 3 Thoughts to “LeetCode 88. Merge Sorted Array”

1. Vicky says:

class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
for (int i = m; i < (m+n); i++) {
nums1[i] = nums2[i – m];
}

Arrays.sort(nums1);
}
}

2. Vicky says:

/** Java solution */

public void merge(int[] nums1, int m, int[] nums2, int n) {
int insertP = m + n – 1;
int nums1P = m – 1;
int nums2P = n – 1;
while (nums1P >= 0 && nums2P >= 0){
if (nums1[nums1P] > nums2[nums2P]) {
nums1[insertP–] = nums1[nums1P–];
}
else {
nums1[insertP–] = nums2[nums2P–];
}
}
while (nums2P >= 0) {
nums1[insertP–] = nums2[nums2P–];
}
}