Merge Without Extra Space | 07 July POTD | C++ | Geeks for Geeks Problem of the Day

Hi I hope you were able to understand the problem solution. Here are a few links for you to check out.

Subscribe and Keep Coding.

#GFG #POTD #geeksforgeeks #problemoftheday #competetiveprogramming #c++

[ashlok]

Just learned a New approach, Thanks brother...😊

[salmankhader]

The given code implements a simple approach to merge two sorted arrays, arr1 and arr2, into a single sorted array. Here is the step-by-step approach:

Initialize two pointers, i and j, with the values n-1 and 0 respectively. These pointers will be used to traverse arr1 and arr2.

Enter a while loop that continues as long as i is greater than or equal to 0 and j is less than m. This loop will compare elements from arr1 and arr2 and place them in the correct order.

Inside the while loop, compare arr1[i] with arr2[j]. If arr1[i] is greater than arr2[j], it means arr1[i] should be placed after arr2[j] in the merged array. Swap the elements arr1[i] and arr2[j] to achieve this.

Decrement i and increment j to move the pointers to the next elements in arr1 and arr2 respectively.

If arr1[i] is not greater than arr2[j], it means we have reached a point where all elements in arr1 are smaller than or equal to the elements in arr2. In this case, break out of the while loop.

After merging the elements in the while loop, both arr1 and arr2 are partially sorted. Sort the remaining elements in each array using Arrays.sort(arr1) and Arrays.sort(arr2).

The merged and sorted array is now stored in arr1 and arr2.

Note: It's important to ensure that both arr1 and arr2 are sorted before merging them. Otherwise, the merged array will not be sorted correctly.


CPP solution :-
void merge(long long arr1[], long long arr2[], int n, int m)
{
int i=n-1, j=0;
while(i>=0 && j<m){
if(arr1[i]>arr2[j])swap(arr1[i--], arr2[j++]);
else break;
}
sort(arr1, arr1+n);
sort(arr2, arr2+m);
}


JAVA solution :-
public static void merge(long arr1[], long arr2[], int n, int m)
{
int i=n-1;
int j=0;

while(i>=0 && j<m){
if(arr1[i]>arr2[j]){
long temp=arr1[i];
arr1[i]=arr2[j];
arr2[j]=temp;
i--;
j++;
}
else{
break;
}
}
Arrays.sort(arr1);
Arrays.sort(arr2);
}

[Lucifer-spam]

Instead of running a for loop for setting the value of base, you can also do (1 << 25) - 1

[reverbmusic]

I did it using a 3rd array and it passed all test cases

[nipamparmar]

i am doing it in time compexity o(nlogm) still its showing tle
they sais that expected time complexity is o((n+m)log(n+m))
here is my solution
class Solution{

public:
//Function to merge the arrays.
void merge(long long arr1[], long long arr2[], int n, int m)
{
// code here
int j=0;
int i=0;
long long temp;
while(i<n)
{
if(arr1[i]>arr2[j])
{
temp=arr1[i];
arr1[i]=arr2[j];
arr2[j]=temp;
i++;
sort(arr2, arr2+m);
}
else
i++;
}


}
};

[fardeensayyed]

Sir, mai programming language Sikh Raha hu mai YouTube video dekhke concept tho Sikh leta hu lakin usko implement nhi karpata baar baar solution dekhna padta hai please kuch tips do

[Dineshkumar_dk]

why we are taking 25 bits when integer is 32 bits, long is 32 bits and long long is 64 bits.