Last Updated: 10 Dec, 2020
Merge K Sorted Arrays
Moderate
Asked in companies
You have been given ‘K’ different arrays/lists, which are sorted individually (in ascending order). You need to merge all the given arrays/list such that the output array/list should be sorted in ascending order.
Input Format :
The first line of input contains an integer T, the number of test cases.
The first line of each test case contains an integer that denotes the value of K.
The next 2*K lines of each test case follow:
The first line contains an integer ‘N’ denoting the size of the array.
The second line contains N space-separated integers.
Output Format :
The first and only line of output contains space-separated elements of the merged and sorted array, as described in the task.
Note :
You don’t have to print anything; it has already been taken care of. Just implement the function.
Constraints :
1 <= T <= 5
1 <= K <= 5
1 <= N <= 20
-10^5 <= DATA <= 10^5
Time Limit: 1 sec
Approaches
- Create an output array ‘RESULT’.
- Traverse all the given arrays from start to end and insert all the elements in the output array ‘RESULT’.
- Sort the ‘RESULT’ and return it.
The idea is based on the divide and conquer strategy. We take pairs of arrays at each step. Then merge the pairs using the two-pointer technique of merging two sorted arrays. Thus, after merging all the pairs, the number of arrays will reduce by half.
We will continue this till the number of remaining arrays doesn’t become 1.
Algorithm:
- Create a recursive function which takes ‘K’ arrays and returns the output array.
- In the recursive function, if the value of ‘K’ is 1 then return the array else if the value of ‘K’ is 2 then merge the two arrays in linear time using two-pointers and return the merged array.
- If the value of ‘K’ is greater than 2, then divide the group of ‘K’ arrays into two equal halves and recursively call the function, i.e 0 to K/2 array in one recursive function and K/2 to ‘K’ array in another recursive function.
- Return the output array.
The idea is to use the concept of min-heap. As we know, the root of the min-heap is always the minimum element in the heap. Thus, insert the first elements of all the ‘K’ arrays into the heap along with their indices, and then removing the minimum ( root ) element and adding it to the output array will give us the required result. We will store indices into the heap because we can get the next greater element from the same array where the current element has been popped.
Algorithm:
- Create an output array ‘RESULT’.
- Create a min-heap of size K and insert the first element of all the arrays, along with its indices, into the heap.
- The heap is ordered by the element of the array/list.
- While the min-heap is not empty, we will keep doing the following operations :
- Remove the minimum element from the min-heap (the minimum element is always at the root) and store it in the output array.
- Insert the next element from the array for which the current element is extracted. If the array doesn’t have any more elements i.e. if the index of the above-removed component is equal to ‘LENGTH-1’ of the array from which the element is extracted, then do nothing. Because we are done with this array.
- After the above process, 'RESULT' will contain all the elements of ‘K’ arrays in ascending order.
- Return the output array i.e. ‘RESULT’.