Merge K Sorted Array

[tanishagarg1803]

Is your feature request related to a problem? Please describe. Merge k Sorted Arrays Medium Accuracy: 51.19% Submissions: 39846 Points: 4 Given K sorted arrays arranged in the form of a matrix of size K*K. The task is to merge them into one sorted array. Example 1:

Input: K = 3 arr[][] = {{1,2,3},{4,5,6},{7,8,9}} Output: 1 2 3 4 5 6 7 8 9 Explanation:Above test case has 3 sorted arrays of size 3, 3, 3 arr[][] = [[1, 2, 3],[4, 5, 6], [7, 8, 9]] The merged list will be [1, 2, 3, 4, 5, 6, 7, 8, 9]. Example 2:

Input: K = 4 arr[][]={{1,2,3,4}{2,2,3,4}, {5,5,6,6},{7,8,9,9}} Output: 1 2 2 2 3 3 4 4 5 5 6 6 7 8 9 9 Explanation: Above test case has 4 sorted arrays of size 4, 4, 4, 4 arr[][] = [[1, 2, 2, 2], [3, 3, 4, 4], [5, 5, 6, 6] [7, 8, 9, 9 ]] The merged list will be [1, 2, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 8, 9, 9 ]. Your Task: You do not need to read input or print anything. Your task is to complete mergeKArrays() function which takes 2 arguments, an arr[K][K] 2D Matrix containing K sorted arrays and an integer K denoting the number of sorted arrays, as input and returns the merged sorted array ( as a pointer to the merged sorted arrays in cpp, as an ArrayList in java, and list in python)

Expected Time Complexity: O(K2*Log(K)) Expected Auxiliary Space: O(K)

Constraints: 1 <= K <= 100

Describe the solution you'd like Algorithm:

Create a min Heap and insert the first element of all k arrays. Run a loop until the size of MinHeap is greater than zero. Remove the top element of the MinHeap and store the element in list. Now insert the next element from the same array in which the removed element belonged. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree.

Describe alternatives you've considered A clear and concise description of any alternative solutions or features you've considered.

Additional context Add any other context or screenshots about the feature request here.

[tanishagarg1803]

please assign this issue to me. i want to contribute in your rep for hacktoberfest 2021

[aark06]

I'd like to work on this issue in Java. Please assign it to me.

[super-pankaj]

Please assign this issue to me. I would like to solve this issue in C++.