Merge Two Arrays Without Extra Space And Print In Sorted Order

Prashant | Thu, 04 Jun, 2020 | 362

Merge arrays without extra space and print in sorted order

We are given two arrays and we are asked to merge two arrays and print it in sorted order.

So we can easily do it when we can add elements in third array then sort it, but wait here is what we are restricted to do.

we are not allowed to use any extra space.

Isn't is a fun task ?

Lets do it in a very simple way.

Logic explanation 

We are asked to sort and print two arrays without using extra space, so what can we do is we can just add all elements in one array.

and then directly sort it.

That will take very less space.

But one more way we can do is that we can add all elements in one array while taking input only, just think and act smart. 😃😎.

Question :- 

Given two sorted arrays arr1[] and arr2[] in non-decreasing order with size n and m. The task is to merge the two sorted arrays into one sorted array (in non-decreasing order).

Note: Expected time complexity is O((n+m) log(n+m)). DO NOT use extra space.  We need to modify existing arrays as following.

Input: arr1[] = {10};
       arr2[] = {2, 3};
Output: arr1[] = {2}
        arr2[] = {3, 10}  

Input: arr1[] = {1, 5, 9, 10, 15, 20};
       arr2[] = {2, 3, 8, 13};
Output: arr1[] = {1, 2, 3, 5, 8, 9}
        arr2[] = {10, 13, 15, 20} 

Input:
First line contains an integer T, denoting the number of test cases. First line of each test case contains two space separated integers X and Y, denoting the size of the two sorted arrays. Second line of each test case contains X space separated integers, denoting the first sorted array P. Third line of each test case contains Y space separated integers, denoting the second array Q.

Output:
For each test case, print (X + Y) space separated integer representing the merged array.

Constraints:
1 <= T <= 100
1 <= X, Y <= 5*104
0 <= arr1iarr2i <= 109

Example:
Input:
2
4 5
1 3 5 7
0 2 6 8 9
2 3
10 12
5 18 20

Output:
0 1 2 3 5 6 7 8 9
5 10 12 18 20

Explanation:
Testcase 1: 
After merging two non-decreasing arrays, we have, 0 1 2 3 5 6 7 8 9.

Solution (optimal in terms of space complexity)

#include<bits/stdc++.h>
using namespace std;
int main() {
	int n,i,j;
	cin>>n;
	for(i=0;i<n;i++)
	{
	    int a,b;
	    cin>>a>>b;
	    int arr[a+b];
	    for(j=0;j<a+b;j++)
	        cin>>arr[j];
	    
	    sort(arr,arr+j);
	    
	    for(j=0;j<a+b;j++)
	        cout<<arr[j]<<" ";
	        
	   cout<<endl;
	}
	return 0;
}

 

Hope you like what we did 😎😁.

 

0 comments
Leave a comment