K-Way Merge
Two sorted lists merge with two pointers: take the smaller head each step and never look back. The wall you hit is k lists, where "which head is smallest" stops being one comparison and becomes a scan of k candidates on every single step. A min-heap turns that scan into an O(log k) pop, which drags the whole merge down to O(n log k) with n elements across all the sequences.
The Pattern: To merge k sorted sequences, maintain a min-heap of size k containing the current "head" of each sequence. Always pop the smallest, then push the next element from that sequence.
Time: O(n log k) where n is total elements. The heap never exceeds k elements.
Time: O(n log k) where n is total elements. The heap never exceeds k elements.
What's inside
- 1 problem, worked step by step
- about 25 min
Premium lessonData Structures & Algorithms
Keep going with Premium.
All 78 lessons and 103 worked problems in this course, plus what 100 companies ask, pulled from 20,000+ candidate reports.
100 companies. Checked every month.
Unlock the full course$49 a year · less than $1 a week · Cancel anytime