Merge two arrays by satisfying given constraints

Given two sorted arrays X[] and Y[] of size m and n each where m >= n and X[] has exactly n vacant cells, merge elements of Y[] in their correct position in array X[] i.e. merge (X, Y) by keeping the sorted order.

 

For example,


Input:
X[] = { 0, 2, 0, 3, 0, 5, 6, 0, 0}
Y[] = { 1, 8, 9, 10, 15 }

The vacant cells in X[] is represented by 0

Output:
X[] = { 1, 2, 3, 5, 6, 8, 9, 10, 15 }

 


 

The idea is very simple. We initially move non-empty elements of X[] in the beginning of X[] and then merge X[] with Y[] starting from end. The merge process is similar to merge routine of mergesort algorithm.

C++

Download   Run Code


Java

Download   Run Code



Output:

1 2 3 5 6 8 9 10 15

 
The time complexity of above solution is O(m + n) and auxiliary space used by the program is O(1).
 

Exercise:
Merge arrays in descending order.
 

Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz