Question : Merge two sorted array without extra space;
My approach;
i used second array B as a min heap. For each element in A (size n) , i compared it with
B[0], if i A[i] is greater than B[0] each time ,then i swapped it. and maintained my min heap B (size m) ( using make_heap in log m);
so my complexity should be n*logm and with given constraints ( n,m < 5x10^4) my code should calculate in < 1sec ??
My code:
You are rebuilding the heap in each step which is O(m log m) each step making the overall complexity O(mn log m). The correct way to do this is in each step, first pop the minimum element from the heap and then push the new element (which is either the same element or the current a[i]). Popping and pushing both take O(log m) time and thus the complexity becomes O(n log n).
U can actually do this in O(m+n) to get the expected output.
use 2 iterators one for each array to traverse.
start from 0 index for both arrays, output the element that is smaller then increment the iterator corresponding to that array.
At last output the remaining elements that are left out.
p.s. U can use vectors and clear to use 0 space
void solve1()
{
int n,m;cin>>n>>m;
int arr[n],brr[m];
for(int i=0;i<n;i++)
{
cin>>arr[i];
}
for(int i=0;i<m;i++)
{
cin>>brr[i];
}
int i=0,j=0;
while(i<n&&j<m)
{
if(arr[i]>brr[j])
{cout<<brr[j]<<" ";j++;}
else
{cout<<arr[i]<<" ";i++;}
}
while(i<n)
{
cout<<arr[i]<<" ";i++;
}
while(j<m)
{
cout<<brr[j]<<" ";j++;
}cout<<endl;
}
This helped me.
Thanks
thanks for reply. appreciate ur suggestion .
In this question. outputs are the modified arrays itself.
so we need to find a way to modify both arrays and get desired two output arrays.
thanks man.