Problem of the day
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.
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.
1 <= T <= 5
1 <= K <= 5
1 <= N <= 20
-10^5 <= DATA <= 10^5
Time Limit: 1 sec
1
2
3
3 5 9
4
1 2 3 8
1 2 3 3 5 8 9
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].
1
4
3
1 5 9
2
45 90
5
2 6 78 100 234
1
0
0 1 2 5 6 9 45 78 90 100 234
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].
Copy the values and sort the final array.
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)).
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).