Given K sorted arrays arranged in form of a matrix of size K*N, you are required to merge them into single sorted array.
The problem basically asks you to find the sorted array of entire matrix using the property that the arrays are already sorted and keeping in mind about the time constraints.
The first line of input is the T number of test cases, each test case consist of K and N the number of arrays and size of each array.
Print the sorted form of merged arrays for each test case in separate line.
Input: T=1 K=3,N=3 1 2 3 4 5 6 7 8 9 Output: 1 2 3 4 5 6 7 8 9 as this is the possible sorted array after merging them into single unit.
The basic naive method to approach this method to create an array of size (k*N) and store all the elements of the given matrix and then sort the entire array of given size and print that array. But the time complexity for that method would be huge as O(K*N*log(K*N)), and there is no use of the condition that the array is already sorted.
The optimized method to solve the given problem is with the help of min-heap.
Following steps are used in the heap method:
Time complexity for this approach in the worst case is: O(K*N*log(K))
Space complexity for this approach in the worst case is: O(K*N)