DEV Community

Cover image for 🎯Merge two sorted arrays without using any extra space🎯
Kaiwalya Koparkar
Kaiwalya Koparkar

Posted on

🎯Merge two sorted arrays without using any extra space🎯

Question:

Given two sorted arrays arr1[] of size N and arr2[] of size M. Each array is sorted in non-decreasing order. Merge the two arrays into one sorted array in non-decreasing order without using any extra space.

Example 1:

Input:
N = 4, M = 5
arr1[] = {1, 3, 5, 7}
arr2[] = {0, 2, 6, 8, 9}
Output: 0 1 2 3 5 6 7 8 9
Explanation: Since you can't use any 
extra space, modify the given arrays
to form 
arr1[] = {0, 1, 2, 3}
arr2[] = {5, 6, 7, 8, 9}
Enter fullscreen mode Exit fullscreen mode

Logic :

  1. Compare and swap method :
    • Take input as two sorted arrays and there sizes a[ ], b[ ], n ( length of a ), m ( length of b)
    • take two varible k = n-1 & j = 0
    • run a while loop from k = n-1 to k = 0 and j = 0 to j = m-1;
    • check if a[ i ] > b [ j ]. If yes swap them . If no k - - and j++;
    • after the while loop sort both the array and print them
import java.util.*;

public class Solution{
    public static void main(String args[]){
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int a[] = new int[n];
        for(int i = 0; i < a.length; i++){
            a[i] = sc.nextInt();
        }
        int b[] = new int[m];
        for(int i = 0; i < b.length; i++){
            b[i] = sc.nextInt();
        }

        //This is swapping approach
        int k = n-1, j = 0;
        while(k >=0 && j <= m){
            if(a[k] > b[j]){
                int temp = a[k];
                a[k] = b[j];
                b[j] = temp;
            }
            k--;
            j++;
        }
        Arrays.sort(a);
        Arrays.sort(b);

        System.out.println("Sorted array is: ");
        for(int i = 0; i < a.length; i++){
            System.out.print(a[i]+" ");
        }
        for(int i = 0; i < b.length; i++){
            System.out.print(b[i]+" ");
        }
    }
}
Enter fullscreen mode Exit fullscreen mode

Top comments (9)

Collapse
 
trueneu profile image
Pavel Gurkov

Do you think it's an optimal solution or it can be improved?

Collapse
 
kaiwalyakoparkar profile image
Kaiwalya Koparkar

This is an O(n) Solution whereas all others are O(n^2). According to me, any other optimal method would take the same O(n) time. So according to me, this is one of the optimal approaches. If you get one lesser than this please do let me know...😀

Collapse
 
trueneu profile image
Pavel Gurkov

Um, this is not O(n) but O(nlogn), unless you can sort in linear time.

And there are a number of others with the same upper limit.

It seems to me that this cannot be done linearly, but I wanted to ask what's your thoughts on this.

Thread Thread
 
kaiwalyakoparkar profile image
Kaiwalya Koparkar

I got your point. I found this as the only optimal way (As far as I found)

Collapse
 
aizuliswafaza profile image
aizuliswafaza

I prefer to turn the array into a list then use the .AddList function to cmerge the second lists then call the .sort function for sorting.

how about that? maybe this method is not very good either.

Collapse
 
kaiwalyakoparkar profile image
Kaiwalya Koparkar

Yeah, you are right but I don't think the interviewer will like you using inbuilt library functions.🙄

Collapse
 
trueneu profile image
Pavel Gurkov • Edited

Kaiwalya, that didn't stop you from using the built-in sort, right?

aizuliswafaza, the problem is different here: the moment you convert this array into a list, you break the constraint on using constant additional memory.

Thread Thread
 
kaiwalyakoparkar profile image
Kaiwalya Koparkar

That's true

Collapse
 
anuraganonymous profile image
Anurag-anonymous • Edited

while(k >=0 && j <= m) this should be like this while(k >=0 && j < m)
please let me know if i am correct
new here😊