# Merge two sorted Arrays (take O(1) space)

Two arrays are given. The elements of these arrays are sorted . Your task is to merge those arrays in a maaner such that  initial numbers are in the first array and the remaining numbers are in the second array.
Input: ar1[] = {10} ar2[] = {2, 3};
Output: ar1[] = {2} ar2[] = {3, 10}
Input: ar1[] = {1, 5, 9, 10, 15, 20} ar2[] = {2, 3, 8, 13};
Output: ar1[] = {1, 2, 3, 5, 8, 9} ar2[] = {10, 13, 15, 20}

Brute Solution :

Lets say you have two array , array a1={1,3,4,9} and second array as a2={2,6,8}
Now you take another array i.e. a3 which size is equal to addition of size of a1 and a2 (n1=size of array a1 and n2= size of array a2).
Plug all the elements from a1 into a3 and all the elements from a2 into a3 and once its done .
Now your a3 looks like ; a3={1,3,4,9,2,6,8}.
Sort array a3 so you will get sorted array.
Now looks ; a3={1,2,3,4,6,8,9}
Take out the first element and place it in a1. (a1={1,……..}
In this way take first n1 elements from a3 and place it in a1 , so your a1 look like : a1={1,2,3,4}.
similarly next n2 elements from a2 and place it in a2.
So now you will have resultant a1 and a2 as ; a1={1,2,3,4} and a2={6,8,9}

Time complexity : O(nlogn)
Spcae complexity : O(n)

Optimal Solution : O(1) space is allowed
As both the arrays that are given are already sorted so we need to take advantage of it so what we can do is we can linearly traverse for the first array. a1={1,3,4,9} and a2={2,6,8}
We see that first element in a1 is 1.Now if we see between 1 and 2 , 1 is at right place . But next time we can see 3 ; is actually greater than this 2.So we know that all the elements towards the right will be greater than 3 and all the elements towards the right of 2 will be greater than 2 . So at position a1 we should have 2 so we will move 2 over here and we will bring 3 to a2.
Once it is swapped the next task is to make the array a2 sort again because our algorithm is based on the fact that both the arrays are sorted we pick the element a2 and insert it at its correct position.
Now your arrays look like this :
a1={1,2,4,9}
a2={3,6,8}
We will repeat this , till we complete the first array .
Linear traversal over here takes n1 and reordering it takes n2 so the total complexity will be O(n1*n2) while the space complexity remains O(1) .

Code :
Merge function for O(1) space :

``````

class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { for(int i=0;i<m;i++)
{
if(nums1[i]>nums2 )
{

swap(nums1[i],nums2);

int first=nums2;

int k;
for(k=1;k<n and nums2[k]<first;k++)
{
nums2[k-1]=nums2[k];
}

nums2[k-1]=first;

}

}

int j=0;

for(int i=m;i<m+n and j<n;i++)
{
nums1[i]=nums2[j];
j++;

}

}
};``````