Merge k sorted price feeds

Question

You have k sorted lists (each ascending) and want a single sorted list of everything. Merge them in O(N \log k) where N is the total number of elements. Concatenating and re-sorting is O(N \log N).

Accepted Answer

At every step the next output element is the smallest among the current fronts of the k lists. A min-heap holding one entry per list, keyed on the front value, hands you that smallest in O(\log k). Pop it, append it, then push the next element from the same list. Store (value, listindex, elementindex) so you know where to advance. Tracing the example: the heap starts with (1,0,0), (1,1,0), (2,2,0). Pop (1,0,0), output 1, push (4,0,1). Pop (1,1,0), output 1, push (3,1,1). Pop (2,2,0), output 2, push (6,2,1), and so on, producing [1, 1, 2, 3, 4, 4, 5, 6]. The heap holds at most k entries, so ea…

Merge k sorted price feeds

Your answer

More Coding questions