Hello, Could you please provide me with a more efficient solution, because this does not seem right.
If what I have done is a good solution, do let me know.
Yours Sincerely,
Ajay Bhat.
Merge K Sorted Arrays
Hello Ajay, your solution is a quite simple solution but it is not the most efficient solution since your solution has complexity of O(n * k log (n * k)) which is equivalent to just merging all the arrays and sorting it. What you fail to use to your advantage here , is the fact, that the arrays given to you are already sorted. Here’s a hint, look up for how to solve this problem for 2 sorted arrays instead of k and you will probably come up with the solution yourself. and if you are unable to, I’d be happy to help.
I modified my code by maintaining an array of pointers, and incrementing the pointer where the minimum among k elements is held. This is the method done in the case of merging 2 sorted arrays. Kindly advice if improvement is needed. Regards, Ajay Bhat.
This is a perfect approach.
This method was quite tricky in the sense that, I had to take care of the edge cases where I had to make sure the pointer index does not over lap with the next array elements and so on. Should we expect questions that are of this difficulty during Interviews ?
Yes, this is quite frequently asked in interview
Okay, thank you for your time Sir.