Pattern Recognition Drill
Medium Heaps
The Problem
Given k sorted arrays, merge them into one sorted array.
What approach would you use?
Think about it before scrolling down.
Min-heap of size k: (value, array_idx, element_idx). Pop min, push next from same array. O(N log k).
Merge pairs of arrays recursively (like merge sort). O(N log k) same complexity.
Common Trap
Merging arrays one by one (array1 + array2, then + array3...) is O(N*k) — much worse.