Show Buttons
Share On Facebook
Share On Twitter
Share On Google Plus
Share On Linkdin
Share On Reddit
Contact us
Hide Buttons

Merge K-sorted Arrays


Problem :

Given k sorted arrays of size n, merge all the k arrays into one sorted array.


Example :

var n_k_arr = [ [ 8, 10, 12 ], [ 6, 9, 13 ], [ 14, 19, 20] ];

output = [ 6, 8, 9, 10, 12, 13, 14, 19, 20 ];


Naive Solution :

  • Merge all the elements into a single array which takes O (nk) time

  • Sort the nk size array which take O( nk log(nk) )


Efficient Solution :

We can merge arrays in O( nk log(k) ) time using Min Heap. Following is detailed algorithm.

  •  Create an output array of size nk
  • Create a min heap of size k and insert 1st element in all the arrays into the heap
  • Repeat following steps nk times
    • Get minimum element from heap ( which takes constant time ) and store it in output array.
    • Replace heap root with next element from the array from which the element is extracted. If the array doesn’t have any more elements, then replace root with infinite. After replacing the root, heapify the tree

 


 

You may also like...

Leave a Reply

Your email address will not be published. Required fields are marked *