visual walkthrough
Kth Smallest Element in a Sorted Matrix
Counting elements ≤ mid across a sorted matrix.
The idea
You can't binary search positions here (the matrix isn't one sorted list), but you can binary search the value.
"How many numbers are ≤ v?" grows with v, and sorted rows and columns let you count it with one staircase walk.
Complexity
| approach | time | space |
|---|---|---|
| Flatten and sort | O(n² log n) | O(n²) |
| Binary search on the value | O(n log(max − min)) | O(1) |