The challenge
Return the kth smallest matrix entry, counting duplicate values separately.
Nonempty rectangular matrix; rows AND columns sorted nondecreasingly. 1 ≤ k ≤ r*c; entries are signed 32-bit integers.
Example
[[1, 5, 9], [10, 11, 13], [12, 13, 15]], k = 8 → 13.
Use the walkthrough below to inspect the input and each state change.
See Matrix value search, step by step
Inspect the comparison, the invariant, and the next boundary.
Answer-space searchk = 8
| r / c | 0 | 1 | 2 |
|---|---|---|---|
| 0 | 1 | 5 | 9 |
| 1 | 10 | 11 | 13 |
| 2 | 12 | 13 | 15 |
Tested candidate / qualifying inputResolved positionParameters shown above
- Left
- 1
- Middle
- —
- Right
- 15
Step 01 / 6
Search the answer range
The candidate is a number, rather than an input index. Keep the smallest feasible value.
left = 1; right = 15Recorded result so far
Not resolved
View exact input
Matrix: [[1,5,9],[10,11,13],[12,13,15]] · k = 8
Put it into code
Search values rather than indices. For a candidate mid, count entries ≤ mid using a staircase from the bottom-left.
Indices are zero-based. C++ uses C++17 or later.
def kth_smallest_matrix(matrix, k):
# Nonempty rectangular matrix, rows AND columns sorted; 1 <= k <= r*c.
rows, cols = len(matrix), len(matrix[0])
left, right = matrix[0][0], matrix[-1][-1]
while left < right:
mid = left + (right - left) // 2
row, col, count = rows - 1, 0, 0
while row >= 0 and col < cols:
if matrix[row][col] <= mid:
count += row + 1
col += 1
else:
row -= 1
if count < k:
left = mid + 1
else:
right = mid
return left#include <vector>
long long kth_smallest_matrix(const std::vector<std::vector<int>>& matrix, int k) {
int rows = static_cast<int>(matrix.size()), cols = static_cast<int>(matrix[0].size());
long long left = matrix[0][0], right = matrix.back().back();
while (left < right) {
long long mid = left + (right - left) / 2, count = 0;
int row = rows - 1, col = 0;
while (row >= 0 && col < cols) {
if (matrix[row][col] <= mid) { count += row + 1; ++col; }
else --row;
}
if (count < k) left = mid + 1;
else right = mid;
}
return left;
}