Problem - Find Kth Smallest (Fourth problem)

Given an $n \times n$ matrix where each row and column is sorted in ascending order, find the $k$-th smallest element.

The naive approach is to flatten the matrix, sort it, and pick the $k$-th element. That takes $O(n^2 \log n)$ time.

But you can use binary search on the value range (not the indices). The answer lies between the smallest and largest elements, and you can count how many elements are smaller than a given value. Think about how logarithms appear here.