 # LeetCode #88 Merge Sorted Array Solution & Explanation

Content

## LeetCode Problem

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

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

## Solution

Please be adviced that the problem’s description- “The final sorted array should not be returned by the function, but instead be stored inside the array nums1″

### C# Solution

Solution1

``````public class Solution {
public void Merge(int[] nums1, int m, int[] nums2, int n) {

int cnt = 0;
for(int i = m;i<nums1.Length;i++)
{
nums1[i] = nums2[cnt];
cnt++;
}
Array.Sort(nums1);
}
}``````

The time complexity  should be : m-n times + Array.Sort ( based on Quicksort ) ➡ O(n)+O(n log n)

But look at the follow up : “Can you come up with an algorithm that runs in O(m + n) time?”

Maybe we should try another way?

Solution2 (Recommend – two pointer solution)

``````public class Solution {
public void Merge(int[] nums1, int m, int[] nums2, int n) {

int index = m+n-1;  //last index
while(n>0)
{
if(m>0 && nums1[m-1]>nums2[n-1])
{
nums1[index] = nums1[m-1];
m--;
}
else
{
nums1[index] = nums2[n-1];
n--;
}
index --;
}
}
}``````

What we want to do is combine nums2 n element with nums1 m element to original nums1.

So if we want to combine and sort together, we need to compare the element of two array in iteration.

Time Complexity :  O(m + n)

### Java Solution

Solution1

``````class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int cnt = 0;
for(int i = m;i<nums1.length;i++)
{
nums1[i] = nums2[cnt];
cnt++;
}

Arrays.sort(nums1);
}
}``````

Runtime : 1ms

Solution2

``````class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
int index = m+n-1;  //last index
while(n>0)
{
if(m>0 && nums1[m-1]>nums2[n-1])
{
nums1[index] = nums1[m-1];
m--;
}
else
{
nums1[index] = nums2[n-1];
n--;
}
index --;
}
}
}``````

Runtime : 0ms

### Python3 Solution

Solution1

``````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.
"""
cnt = 0;
while(m < len(nums1)):
nums1[m] = nums2[cnt];
cnt+=1
m+=1
nums1.sort();``````

Runtime : 78ms、46ms、54ms ➡ average 59ms

Solution2

``````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.
"""
index = m+n-1

while(n>0):
if(m>0 and nums1[m-1]>nums2[n-1]):
nums1[index] = nums1[m-1];
m-=1;

else:
nums1[index] = nums2[n-1];
n-=1;

index -=1;``````

Runtime : 59ms、70ms、30ms ➡ average 53ms

### JavaScript Solution

Solution1

``````/**
* @param {number[]} nums1
* @param {number} m
* @param {number[]} nums2
* @param {number} n
* @return {void} Do not return anything, modify nums1 in-place instead.
*/
var merge = function(nums1, m, nums2, n) {
var index = m+n-1;  //last index
while(n>0)
{
if(m>0 && nums1[m-1]>nums2[n-1])
{
nums1[index] = nums1[m-1];
m--;
}
else
{
nums1[index] = nums2[n-1];
n--;
}
index --;
}
};``````

Runtime : 97ms、109ms、64ms

## Conclusion

How to reduce time complexity always is a interesting question of coding.

In this case, you can use a iteration with two pointers to avoid using Array.sort function (List.sort…, etc)

```"Eventually, all things merge into one, and a river runs through it."
- Norman Maclean                                                                                                                                         ```

The problem link : Merge Sorted Array – LeetCode

Reference

Technology Article

Related Post