315. Kth Smallest Element in a Sorted Matrix
You are given an n × n integer matrix matrix in which every row is sorted left to right and every column is sorted top to bottom (both non-decreasing), plus an integer k.
Return the k-th smallest value in the matrix, counting positions, not distinct values — if a value appears three times, it occupies three slots in the sorted order. k is 1-based: k = 1 asks for the minimum, k = n² for the maximum.
The whole matrix has n² entries, but the interesting solutions never materialize that flat sorted list. Aim for better than O(n²) memory — the best-known approach runs in O(n log(max − min)) time and O(1) extra space.
Example 1:
Input: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Output: 13
Explanation: All nine entries in sorted order are 1, 5, 9, 10, 11, 12, 13, 13, 15. The value 13 appears twice and fills slots 7 and 8, so the 8th smallest is 13.
Example 2:
Input: matrix = [[-5]], k = 1
Output: -5
Explanation: A 1 × 1 matrix has a single entry, which is its 1st smallest.
Constraints:
- n == matrix.length == matrix[i].length
- 1 ≤ n ≤ 300
- -10⁹ ≤ matrix[i][j] ≤ 10⁹
- Each row is sorted in non-decreasing order left to right.
- Each column is sorted in non-decreasing order top to bottom.
- 1 ≤ k ≤ n²
Hints:
The matrix is n sorted lists stacked on top of each other. Merging sorted lists is a min-heap job: seed the heap with the first element of every row, then pop k − 1 times — each pop is replaced by the next element of its row.
You can do better by binary searching on the *value*, not a position. For a candidate v, count how many entries are <= v in O(n) with a staircase walk from the bottom-left corner: step right while the entry is <= v, otherwise step up. Find the smallest v whose count reaches k.
The binary-search answer is guaranteed to be an actual matrix entry: if the smallest v with count(v) >= k were absent from the matrix, then count(v − 1) would equal count(v), contradicting v being the smallest.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: matrix = [[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8
Expected output: 13