Pattern Recognition Drill
Medium Heaps
The Problem
Given an n x n matrix where rows and columns are sorted, find the kth smallest element.
What approach would you use?
Think about it before scrolling down.
Min-heap with (value, row, col). Pop k times. Push right and down neighbors. O(k log n).
Binary search on value range [min, max]. Count elements <= mid. O(n log(max-min)).
Common Trap
Flattening and sorting is O(n² log n²). The heap approach exploits the sorted structure.