Identify

• problem will feature sorted arrays, lists, or a matrix
• if the problem asks you to merge sorted lists, find the smallest element in a sorted list
• if the problem giving k ****sorted arrays and asks us to perform a sorted traversal  of all the elements of all arrays
• K-way Merge helps you solve problems that involve a set of sorted arrays

Motive

• whenever you’re given ‘K’ sorted arrays, you can use a Heap to efficiently perform a sorted traversal of all the elements of all arrays
• you can push the smallest element of each array in a Min Heap to get the overall minimum
• after getting the overall minimum, push the next element from the same array to the heap
• then, repeat this process to make a sorted traversal of all elements

Steps

• insert the first element of each array in a Min Heap.
• after this, take out the smallest (top) element from the heap and add it to the merged list
• after removing the smallest element from the heap, insert the next element of the same list into the heap
• repeat steps 2 and 3 to populate the merged list in sorted order

Complexity

Time: O(n log k)

• where n is the total number of elements in all the k input arrays.

Space: O(k)