Merge Without Using Extra Space Geeks For Geeks

class Solution {

    public void merge(int arr1[], int arr2[], int n, int m) {

       

        

        PriorityQueue<Integer> pq=new PriorityQueue<Integer>();

int x=0;

int y=0;

while(x<n && y<m){

if(arr1[x]<arr2[y]){

pq.add(arr1[x]);

x++;

}

else if(arr1[x]==arr2[y]){

pq.add(arr1[x]);

pq.add(arr2[y]);

x++;

y++;

}

else{

pq.add(arr2[y]);

y++;

}

}

for(;x<n;x++){

pq.add(arr1[x]);

}

for(;y<m;y++){

pq.add(arr2[y]);

}

int index=0;

while(index<n){

arr1[index++]=pq.remove();

}

index=0;

while(index<m){

arr2[index++]=pq.remove();

}

    }

}

Approach:

Here we will traverse both the list together and see for smaller element in both lists and simultaneously add it to the priority queue. Value for the pointer will be increased for the list whose elements get add up in the queue. If the same value elements are there then the value for both pointers will be increased simultaneously and both elements will be added to the queue.

After that, if any list elements are untraversed we will add those elements to the queue.

In end, we modify the elements of both arrays removing out elements from the queue according to their sizes.

Here priority queue will remove elements in decreasing order of their priority. So we will first get the minimum value element and then the large value elements, following the natural ordering of the priority queue.

Time: O((n+m)*log(n+m)) [Priority Queue.][GFG Time : 1.4/2.5]

Space: O(1) 

Thanks for Reading.