The k-th smallest value in a sorted matrix
An n × n matrix has every row and every column sorted in non-decreasing order. Return its
k-th smallest value, counting repeated values separately (the k-th in sorted order, not the k-th distinct).
Use less than O(n²) memory.
Examples
| Input | Output | Why |
|---|---|---|
matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8 | 13 | In order: 1, 5, 9, 10, 11, 12, 13, 13, 15. |
matrix = [[-5]], k = 1 | -5 | |
matrix = [[1,2],[1,3]], k = 2 | 1 |
Constraints
- 1 ≤ n ≤ 300
- −10⁹ ≤ matrix[i][j] ≤ 10⁹
- 1 ≤ k ≤ n²
Hints
Hint 1
A heap of row fronts works in O(k log n). Try a different question: for a value x, how many cells are ≤ x?
Hint 2
Count them with the staircase walk from the bottom-left corner: O(n) for the whole matrix.
Hint 3
count(x) never decreases as x grows. The answer is the smallest x with count(x) ≥ k. Search x between the smallest and largest values.
Where people lose marks
- Returning a value that is not in the matrix: the search must find the first x with count ≥ k, not any such x.
- Writing (lo + hi) / 2 in C++, Java or Rust, which truncates toward zero: for lo = −3, hi = −2 it gives −2 = hi, and hi = mid never shrinks the range. lo + (hi − lo) / 2 is the floor whatever the signs.
- Counting distinct values: the k-th smallest counts repeats.
Dry run on [[1,5,9],[10,11,13],[12,13,15]],8
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 6k8
Values run from 1 to 15. For a value x, count the cells ≤ x; the answer is the smallest x with at least 8.
-
Step 2 / 6lo1mid8hi15count ≤ mid2
2 cells hold a value ≤ 8. Fewer than 8: the answer is larger, lo = 9.
-
Step 3 / 6lo9mid12hi15count ≤ mid6
6 cells hold a value ≤ 12. Fewer than 8: the answer is larger, lo = 13.
-
Step 4 / 6lo13mid14hi15count ≤ mid8
8 cells hold a value ≤ 14. That is at least 8: the answer is 14 or smaller, hi = 14.
-
Step 5 / 6lo13mid13hi14count ≤ mid8
8 cells hold a value ≤ 13. That is at least 8: the answer is 13 or smaller, hi = 13.
-
Step 6 / 6answer13
lo = hi = 13: 8 cells are ≤ 13 and only 6 are ≤ 12, so the 8-th smallest is 13.
How to think about it
Positions in this matrix are not in sorted order, so we cannot binary search them. Values, though, are
numbers, and for any value x the number of cells ≤ x can be counted fast. From the
bottom-left corner: if the cell is ≤ x, so is every cell above it in that column, so add the row
index plus one and move right; otherwise move up. That is O(n).
count(x) is non-decreasing in x, and the k-th smallest value is exactly the
smallest x with count(x) ≥ k:
- If
vis the k-th smallest, at leastkcells are≤ v, so it passes. - Any
x < vhas fewer thankcells at or below it, or the k-th smallest would be at mostx.
So search x in [matrix[0][0], matrix[n−1][n−1]] for the first passing value. The
search may test values that appear nowhere in the matrix, and that is fine: the first passing value is always
one that does appear, by the argument above.
Cost: O(n log(max − min)), with O(1) extra memory. Compute the midpoint as
lo + (hi − lo) / 2 with floor division, since the values can be negative.
Complexity. Time O(n log(max − min)) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def kth_smallest(matrix, k):
n = len(matrix)
def count_at_most(x): # staircase walk from the bottom-left corner
r, c, count = n - 1, 0, 0
while r >= 0 and c < n:
if matrix[r][c] <= x:
count += r + 1 # this cell and everything above it
c += 1
else:
r -= 1
return count
lo, hi = matrix[0][0], matrix[-1][-1]
while lo < hi:
mid = (lo + hi) // 2 # floor, also for negatives
if count_at_most(mid) >= k:
hi = mid
else:
lo = mid + 1
return lo#include <vector>
long long solve(const std::vector<std::vector<int>>& matrix, int k) {
const int n = (int)matrix.size();
auto countAtMost = [&](long long x) { // staircase walk from the bottom-left
int r = n - 1, c = 0;
long long count = 0;
while (r >= 0 && c < n) {
if (matrix[r][c] <= x) { count += r + 1; ++c; }
else --r;
}
return count;
};
long long lo = matrix[0][0], hi = matrix[n - 1][n - 1];
while (lo < hi) {
long long mid = lo + (hi - lo) / 2; // hi - lo >= 0, so this is the floor
if (countAtMost(mid) >= k) hi = mid; else lo = mid + 1;
}
return lo;
}class Solution {
private long countAtMost(int[][] m, long x) { // staircase walk from the bottom-left
int n = m.length, r = n - 1, c = 0;
long count = 0;
while (r >= 0 && c < n) {
if (m[r][c] <= x) { count += r + 1; c++; }
else r--;
}
return count;
}
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
long lo = matrix[0][0], hi = matrix[n - 1][n - 1];
while (lo < hi) {
long mid = lo + (hi - lo) / 2; // the floor, also for negatives
if (countAtMost(matrix, mid) >= k) hi = mid; else lo = mid + 1;
}
return (int) lo;
}
}function kthSmallest(matrix, k) {
const n = matrix.length;
const countAtMost = x => { // staircase walk from the bottom-left
let r = n - 1, c = 0, count = 0;
while (r >= 0 && c < n) {
if (matrix[r][c] <= x) { count += r + 1; c++; }
else r--;
}
return count;
};
let lo = matrix[0][0], hi = matrix[n - 1][n - 1];
while (lo < hi) {
const mid = Math.floor((lo + hi) / 2); // floor, also for negatives
if (countAtMost(mid) >= k) hi = mid; else lo = mid + 1;
}
return lo;
}fn solve<const C: usize>(matrix: &[[i64; C]], k: i64) -> i64 {
let n = matrix.len();
let count_at_most = |x: i64| -> i64 { // staircase walk from the bottom-left
let (mut r, mut c, mut count) = (n as i64 - 1, 0usize, 0i64);
while r >= 0 && c < n {
if matrix[r as usize][c] <= x {
count += r + 1;
c += 1;
} else {
r -= 1;
}
}
count
};
let (mut lo, mut hi) = (matrix[0][0], matrix[n - 1][n - 1]);
while lo < hi {
let mid = lo + (hi - lo) / 2; // the floor, also for negatives
if count_at_most(mid) >= k { hi = mid } else { lo = mid + 1 }
}
lo
}import Data.Array
solve :: [[Int]] -> Int -> Int
solve rows k = go (a ! (0, 0)) (a ! (n - 1, n - 1))
where
n = length rows
a = listArray ((0, 0), (n - 1, n - 1)) (concat rows)
-- staircase walk from the bottom-left corner
countAtMost x = walk (n - 1) 0 0
where
walk r c acc
| r < 0 || c >= n = acc
| a ! (r, c) <= x = walk r (c + 1) (acc + r + 1)
| otherwise = walk (r - 1) c acc
go lo hi
| lo >= hi = lo
| countAtMost mid >= k = go lo mid
| otherwise = go (mid + 1) hi
where mid = lo + (hi - lo) `div` 2Variants to try
- k-th smallest of n sorted arrays of different lengths: count with a lower bound in each array.
- Rows sorted but columns not: count with a binary search per row, O(n log n log range).
- With a heap: push the first column, pop k − 1 times, pushing the right neighbour of each popped cell.
Next problems
The k-th smallest entry of a multiplication table
Row i of the table holds i, 2i, …, ni, so it has min(⌊x / i⌋, n) entries ≤ x. Count in O(m) and search for the first value whose count reaches k.
Open the problem → Hard30 minThe k-th smallest distance between two values
There are n²/2 distances, too many to sort. Sort the values, count pairs within distance d by sliding window, and search for the first d whose count reaches k.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem →Write a solution and run it against the real test table.
Keep going
The k-th smallest entry of a multiplication table
Row i of the table holds i, 2i, …, ni, so it has min(⌊x / i⌋, n) entries ≤ x. Count in O(m) and search for the first value whose count reaches k.
Open the problem → Hard30 minThe k-th smallest distance between two values
There are n²/2 distances, too many to sort. Sort the values, count pairs within distance d by sliding window, and search for the first d whose count reaches k.
Open the problem → Easy10 minFind a value in a sorted array
The search every other binary search is built on: halve a closed range until the value is found or the range is empty.
Open the problem → Binary searchThe pattern behind it
Search the answer, not the array: halve a monotone predicate until one candidate is left.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.