Click here to Skip to main content
15,041,788 members
Please Sign up or sign in to vote.
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.

answer:

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

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!
   
Comments
_-_-_-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!
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.
   
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--;
    }
}
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900