Merge K Sorted Arrays

Moderate
0/80
Average time to solve is 15m
230 upvotes
Asked in companies
MathworksMicrosoftOracle

Problem statement

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.

Detailed explanation ( Input/output format, Notes, Images )
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 
Sample Input 1:
1
2
3 
3 5 9 
4 
1 2 3 8   
Sample Output 1:
1 2 3 3 5 8 9 
Explanation of Sample Input 1:
After merging the two given arrays/lists [3, 5, 9] and [ 1, 2, 3, 8], the output sorted array will be [1, 2, 3, 3, 5, 8, 9].
Sample Input 2:
1
4
3
1 5 9
2
45 90
5
2 6 78 100 234
1
0
Sample Output 2:
0 1 2 5 6 9 45 78 90 100 234
Explanation of Sample Input 2 :
After merging the given arrays/lists [1, 5, 9], [45, 90], [2, 6, 78, 100, 234] and [0], the output sorted array will be [0, 1, 2, 5, 6, 9, 45, 78, 90, 100, 234].
Hint

Copy the values and sort the final array. 

Approaches (3)
Sorting

 

  1. Create an output array ‘RESULT’.
  2. Traverse all the given arrays from start to end and insert all the elements in the output array ‘RESULT’.
  3. Sort the ‘RESULT’ and return it.
Time Complexity

O((N * K) *  log(N * K)), Where ‘K’ is the number of arrays and ‘N’ is the average number of elements in every array.

 

We are traversing all the ‘K’ arrays and then we are sorting the output array. Thus, the total time complexity will be O((N * K) *  log(N * K)). 

Space Complexity

O(N * K), Where ‘K’ is the number of arrays and ‘N’ is the average number of elements in every array.

 

We are using an array/list of size O(N * K) to store all the elements of the ‘K’ arrays/lists. Then, we are sorting the output array in ascending order which takes at-least log(N * K) additional space. Thus, the total space complexity is O(K * N).

Video Solution
Unlock at level 3
(75% EXP penalty)
Code Solution
(100% EXP penalty)
Merge K Sorted Arrays
Full screen
Console