mediumCodingConceptMidSeniorStaff
You are handed k sorted lists and asked for one sorted list. What is wrong with concatenating and sorting?
Nothing about correctness - it works. It throws away the sortedness you were given and pays O of N log N to rebuild it, where merging costs O of N log k, and it requires every element resident at once where a merge requires k. On lists that arrive as streams the second objection is the one that disqualifies it outright.
6 min readUpdated 2026-08-15
Answer
Short answer
Merge k sorted lists with a min-heap that holds the current head of each non-empty list. Repeatedly pop the smallest value, append it, and push the next value from the same source list. This uses O(k) extra memory and O(N log k) time, preserving the sorted order already present in the inputs.
Was this answer helpful?
Likely follow-ups
- The lists are files far larger than memory and the output is a file too. Which part of your answer survives unchanged?
- Merge them in place across the input arrays with no output buffer. What does that cost you?
- One of the k lists is nine tenths of the data. Does anything about your bound or your constants change?
- Each list is sorted by a key you must compute rather than read. Where do you put that computation?
Related questions
- Numbers arrive one at a time and after each one you must answer what the Kth largest so far is. What do you keep, and what do you deliberately throw away?mediumAlso on heaps and priority-queue6 min
- Return the k most frequent elements from a large stream of values. Why not just sort by frequency?mediumAlso on heaps and priority-queue4 min
- Numbers arrive one at a time and after each one I want the running median. How would you keep it?mediumAlso on heaps and priority-queue5 min
- Find the cheapest route between two nodes in a weighted directed graph. Then tell me what breaks if one edge has a negative weight.mediumAlso on priority-queue5 min