15,041,788 members
1.00/5 (1 vote)
See more:
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.

I was able to write the code in O(n) space complexity.

Can we write this code in O(1) space complexity ?

What I have tried:

C++
```void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int i,j=0,k=0;
int a[m+1];
a[m]=0;
for(i=0;i<m;i++)
{
a[i]=nums1[i];
}
i=0;
while(i<m && j<n )
{
if(a[i]<nums2[j])
{
nums1[k++]=a[i++];
}
else
{
nums1[k++]=nums2[j++];
}
}
if(i!=m || j!=n)
{
for(;i<m;i++)
{
nums1[k++]=a[i];
}
for(;j<n;j++)
{
nums1[k++]=nums2[j];
}
}
}```
Posted
Updated 4-Jul-21 19:53pm
KarstenK 20-Jun-21 3:20am

important: what do you do, when some element of array 2 is equal to a element in array 1!
_-_-_-me 20-Jun-21 3:24am

I think it would go to else part.

## Solution 1

No. O(1) requires that it takes the same amount of time to process, regardless of the data sets provided. Obviously, two sets of 1 element will take less time to process than a set of 5000 and a set of 1,000,000 will - so O(1) is not achievable.

But it can be improved. Think about it: both arrays are sorted.
One array is bigger enough to store everything in both.

What would happen if you went from the end of each array instead of the beginning?
Hint: how does a zipper work?

But this is your homework, not mine - so I'll give you no code!
_-_-_-me 20-Jun-21 3:40am

Thank you very much !
According to the hint:
One array is bigger enough to store everything in both.
and
What would happen if you went from the end of each array instead of the beginning?
I understood it why we should only go from end--
We should only go from end to front but not front to end otherwise the nums1 array elements would be disturbed .
and we should start storing elements in decreasing order from end.
I got it.
Thank you!
OriginalGriff 20-Jun-21 4:14am

You're welcome!

## Solution 3

Move the m filled positions of ints1 from [0] ... [m-1] to positions [n] ... [n+m-1]. Now you may merge the arrays into the beginning positions of ints1 without interfering with the input.

## Solution 2

C++
```void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){
int k=m+n-1;
int i=m-1;
int j=n-1;
while(i>=0 && j>=0)
{
if(nums1[i]>nums2[j])
{
nums1[k--]=nums1[i];
i--;
}
else
{
nums1[k--]=nums2[j];
j--;
}
}
while(j>=0)
{
nums1[k--]=nums2[j];
j--;
}
}```