Since we have to insert all elements of all input arrays in to Heap, wouldn’t the time complexity still be N*Log(N)?
There are N elements in total (from all K arrays) and we have to insert each of then in to the Heap.
Course: Grokking the Coding Interview: Patterns for Coding Questions - Learn Interactively
Lesson: Merge K Sorted Lists (medium) - Grokking the Coding Interview: Patterns for Coding Questions
Hi @Peter_Litvak!
If you look into the implementation, we can note that we are popping an element of the heap, and inserting one element in each iteration of the loop. Since we have n elements, the outer loop will do these pop/insert operations n times.
Now, the worst-case time complexity of these two operations is O(log(n)). Since we are dealing with only 1 element from each list, our heap will be having only K elements, and the time complexity of heap operations will be reduced to O(log(K)) instead of O(log(n)). Since these O (log(K)) operations are done for each element, the time complexity will be O(n*log(K)).
Please let us know if you still have any confusion about it.
Thanks.