| Random Link ¯\_(ツ)_/¯ | ||
| Aug 1, 2022 | » | Sorting and Searching
5 min; updated Aug 1, 2022
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]\).... |