## DEV Community is a community of 617,782 amazing developers

We're a place where coders share, stay up-to-date and grow their careers. # 🎯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}
``````

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]+" ");
}
}
}
``````

## Discussion (8)  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...😀