Algorithms and Data Structures · Senior · Question 20 of 75
How do you merge k sorted lists with n elements in total efficiently?
- 1Concatenate them and sort the result: O(n)
- 2Merge them one by one into a growing result: O(n)
- ✓Correct answer: A min-heap of the k current heads: O(n log k)
Explanation
Each step pops the smallest head and pushes the next element from the same list. Merging one by one is O(n × k) in the worst case; concatenating and sorting is O(n log n).