Information Processing Letters

Order Statistics

K-th Smallest Element in Sorted Matrix

Given an \(N \times N\) matrix, where each of the rows and columns are sorted in ascending order, return the \(k^{th}\) smallest element in the matrix. The memory complexity must be better than \(O(N^2)\).

It’s not guaranteed that matrix[r][c] > matrix[r-1][c], so we can’t compute the row (and similarly, the column) in which the \(k^{th}\) smallest element is in.

Using a priority queue that holds the \(K\) smallest elements does not work because the memory usage is \(O(K)\), where \(K\) can be any value in \([1, N^2]\). Furthermore, that doesn’t take into account that the rows and columns are already sorted.