# Merge Sorted Arrays Leetcode Solution  Difficulty Level Easy
algorithms Array coding Interview interviewprep LeetCode LeetCodeSolutions Two Pointer

In the problem “Merge Sorted Arrays”, we are given two arrays sorted in non-descending order. The first array is not fully filled and has enough space to accommodate all elements of the second array as well. We have to merge the two arrays, such that the first array contains elements of both the arrays and is sorted in non-descending order.

## Example  ```{1 , 2 , 3 , - , - , -}
{2 , 6 , 7}
```
`1 2 2 3 6 7`
```{1 , 1 , 1 ,  - , -}
{2 , 4}```
`1 1 1 2 4`

## Approach(Sorting)  We can transfer all the elements of the second array to the first one. We can then sort the first array to get the required result.

### Algorithm

1. For i = 0 to i = N, assign
1. a[i + m] = b[i], a =first array, b = second array
2. Sort the first array
3. Print the required result

### Implementation of Merge Sorted Arrays Leetcode Solution

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
for(int i = 0 ; i < n ; i++)
a[i + m] = b[i];

sort(a.begin() , a.end());
return;
}

int main()
{
vector <int> a = {1 , 2 , 3};
vector <int> b = {2 , 6 , 7};

int m = 3 , n = 3;
a.resize(m + n);
merge(a , m , b , n);
for(int &x : a)
cout << x << " ";

return 0;
}
```

#### Java Program

```import java.util.Arrays;

class merge_sorted_array
{
static void merge(int[] a , int m , int[] b , int n)
{
for(int i = 0 ; i < n ; i++)
a[i + m] = b[i];
Arrays.sort(a);
}

public static void main(String args[])
{
int m = 3 , n = 3;

int[] a = new int[m + n];

a = 1;
a = 2;
a = 3;

int[] b = {2 , 6 , 7};
merge(a , m , b , n);

for(int i = 0 ; i < a.length ; i++)
System.out.print(a[i] + " ");
}
}
```
`1 2 2 3 6 7`

### Complexity Analysis of Merge Sorted Arrays Leetcode Solution

#### Time Complexity

O(KlogK), where K = N + M. N = size of the first array, M = size of the second array. As we sort the first array after it has stored all N + M elements.

Find Three Element From Different Three Arrays Such That a + b + c = sum

#### Space Complexity

O(1) as constant memory is used for variables.

## Approach(Two Pointers)  We can use two-pointer technique to merge the two sorted arrays, into a new array. But, the creation of this new array will cost extra space. We can try to avoid this extra array especially when the first array has enough space to hold all the elements of both the arrays. We can use two pointers and start merging the elements in the back of the first array.

This will cut the problem of “extra array memory” as we keep fixing the elements in the void space. ### Algorithm

1. Initialize two variables i and j storing indices of the last element of the first and second array respectively.
• i = M – 1 , j = N – 1
2. Initialize a variable idx, storing the last index of the first array, that is:
• idx = N + M – 1
3. Now, do the following until either of i or j becomes zero
• If a[i] >= b[j]
• Assign a[idx] = a[i], decrement i
• Else
• Assign a[idx] = b[j], decrement j
• Decrement idx
4. Either of i or j is not zero, which means some elements are yet to be merged. As they would already be in a sorted manner, we simply append them to the first array in the front.
5. While i does not become zero,
1. Assign a[idx] = a[i]
2. Decrement idx and i
6. While j does not become zero,
1. Assign a[idx] = b[j]
2. Decrement idx and j
7. Now first array has all the elements in the required sorted order.

### Implementation of Merge Sorted Arrays Leetcode Solution

#### C++ Program

```#include <bits/stdc++.h>
using namespace std;

void merge(vector <int> &a , int m , vector <int> &b , int n)
{
int i = m - 1 , j = n - 1 , idx = m + n - 1;
while(i >= 0 && j >= 0)
{
if(a[i] >= b[j])
{
a[idx] = a[i];
i--;
}
else
{
a[idx] = b[j];
j--;
}
idx--;
}

while(i >= 0)
a[idx--] = a[i--];

while(j >= 0)
a[idx--] = b[j--];

return;
}

int main()
{
vector <int> a = {1 , 2 , 3};
vector <int> b = {2 , 6 , 7};

int m = 3 , n = 3;
a.resize(m + n);
merge(a , m , b , n);
for(int &x : a)
cout << x << " ";

return 0;
}
```

#### Java Program

```import java.util.Arrays;

class merge_sorted_array
{
static void merge(int[] a , int m , int[] b , int n)
{
int i = m - 1 , j = n - 1 , idx = m + n - 1;
while(i >= 0 && j >= 0)
{
if(a[i] >= b[j])
{
a[idx] = a[i];
i--;
}
else
{
a[idx] = b[j];
j--;
}
idx--;
}

while(i >= 0)
a[idx--] = a[i--];

while(j >= 0)
a[idx--] = b[j--];

return;
}

public static void main(String args[])
{
int m = 3 , n = 3;

int[] a = new int[m + n];

a = 1;
a = 2;
a = 3;

int[] b = {2 , 6 , 7};
merge(a , m , b , n);

for(int i = 0 ; i < a.length ; i++)
System.out.print(a[i] + " ");
}
}
```
`1 2 2 3 6 7`

### Complexity Analysis of Merge Sorted Arrays Leetcode Solution

#### Time Complexity

O(N + M). N = size of the first array, M = size of the second array. As we traverse both the arrays once.