Kth Smallest Element in a Sorted Matrix
Kth Smallest Element in a Sorted Matrix is a medium binary search problem solved with the binary search on answer space pattern.
The best approach, optimal (binary search on the value), runs in O(n log R) time and O(1) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (flatten and sort) up.
Problem
You get an n x n integer matrix whose rows are each sorted in non-decreasing order from left to right, and whose columns are each sorted in non-decreasing order from top to bottom. You also get an integer k.
Return the k-th smallest value among all n² entries, counting duplicates separately (it is the k-th value of the fully sorted list, not the k-th distinct value).
Try to use less than O(n²) extra memory.
Examples
Example 1
- Input
matrix = [[2, 6, 9], [3, 8, 12], [7, 10, 15]], k = 5- Output
8- Why
- In sorted order the values are 2, 3, 6, 7, 8, 9, 10, 12, 15; the fifth one is 8.
Example 2
- Input
matrix = [[-4, -4], [-1, 3]], k = 2- Output
-4- Why
- Duplicates count separately: the two smallest values are both -4.
Constraints
n == matrix.length == matrix[i].length,1 <= n <= 300-10^9 <= matrix[i][j] <= 10^9- Every row and every column is sorted in non-decreasing order.
1 <= k <= n²
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (2 examples, or your own). Submit also runs 12 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (flatten and sort) | O(n² log n) | O(n²) |
| Min-heap k-way merge | O(k log n) | O(n) |
| Optimal (binary search on the value) | O(n log R) | O(1) |
1Brute force (flatten and sort)
O(n² log n)Sorting n² values costs O(n² log n²) = O(n² log n).O(n²)The flattened copy.Copy all n² values into one array, sort it, and return the element at index k - 1.
- Copy every entry into a 1D array of size n².
- Sort the array.
- Return arr[k - 1].
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int[] all = new int[n * n];
int idx = 0;
for (int[] row : matrix) {
for (int v : row) all[idx++] = v;
}
Arrays.sort(all);
return all[k - 1];
}
}class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
values = [v for row in matrix for v in row]
values.sort()
return values[k - 1]class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
vector<int> all;
for (auto& row : matrix) {
for (int v : row) all.push_back(v);
}
sort(all.begin(), all.end());
return all[k - 1];
}
};function kthSmallest(matrix, k) {
const all = [];
for (const row of matrix) {
for (const v of row) all.push(v);
}
all.sort((a, b) => a - b);
return all[k - 1];
}2Min-heap k-way merge
O(k log n)k heap operations, each O(log n) because the heap never holds more than n entries.O(n)At most one entry per row in the heap.Treat each row as a sorted list and merge them with a min-heap, like merging k sorted lists. Seed the heap with the first element of each row. Pop the smallest k - 1 times, each time pushing the next element of the same row. The top of the heap is then the k-th smallest.
- Push (matrix[r][0], r, 0) for each row r < min(n, k).
- Repeat k - 1 times: pop (value, r, c); if c + 1 < n, push (matrix[r][c + 1], r, c + 1).
- Return the value at the top of the heap.
class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
for (int r = 0; r < Math.min(n, k); r++) heap.add(new int[] { matrix[r][0], r, 0 });
for (int i = 0; i < k - 1; i++) {
int[] top = heap.poll();
int r = top[1], c = top[2];
if (c + 1 < n) heap.add(new int[] { matrix[r][c + 1], r, c + 1 });
}
return heap.peek()[0];
}
}class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
heap = [(matrix[r][0], r, 0) for r in range(min(n, k))]
heapq.heapify(heap)
for _ in range(k - 1):
_, r, c = heapq.heappop(heap)
if c + 1 < n:
heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
return heap[0][0]class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
priority_queue<tuple<int, int, int>, vector<tuple<int, int, int>>, greater<tuple<int, int, int>>> heap;
for (int r = 0; r < min(n, k); r++) heap.push({matrix[r][0], r, 0});
for (int i = 0; i < k - 1; i++) {
auto [v, r, c] = heap.top();
heap.pop();
if (c + 1 < n) heap.push({matrix[r][c + 1], r, c + 1});
}
return get<0>(heap.top());
}
};class MinHeap {
constructor(cmp = (a, b) => a - b) { this.a = []; this.cmp = cmp; }
size() { return this.a.length; }
peek() { return this.a[0]; }
push(x) {
const a = this.a;
a.push(x);
let i = a.length - 1;
while (i > 0) {
const p = (i - 1) >> 1;
if (this.cmp(a[i], a[p]) >= 0) break;
[a[i], a[p]] = [a[p], a[i]];
i = p;
}
}
pop() {
const a = this.a, top = a[0], last = a.pop();
if (a.length > 0) {
a[0] = last;
let i = 0;
while (true) {
const l = 2 * i + 1, r = l + 1;
let m = i;
if (l < a.length && this.cmp(a[l], a[m]) < 0) m = l;
if (r < a.length && this.cmp(a[r], a[m]) < 0) m = r;
if (m === i) break;
[a[i], a[m]] = [a[m], a[i]];
i = m;
}
}
return top;
}
}
function kthSmallest(matrix, k) {
const n = matrix.length;
const heap = new MinHeap((a, b) => a[0] - b[0]);
for (let r = 0; r < Math.min(n, k); r++) heap.push([matrix[r][0], r, 0]);
for (let i = 0; i < k - 1; i++) {
const [, r, c] = heap.pop();
if (c + 1 < n) heap.push([matrix[r][c + 1], r, c + 1]);
}
return heap.peek()[0];
}3Optimal (binary search on the value)
O(n log R)Each count is O(n) (at most 2n steps), and the binary search runs about log2(2 * 10^9) ≈ 31 times, where R is the value range.O(1)Only a few variables.The answer is a value between matrix[0][0] and matrix[n-1][n-1]. For a guess x, count the entries <= x with a staircase walk: start at the bottom-left; if the entry is <= x, the whole column above it is too, so add row + 1 and step right; otherwise step up. The count only grows as x grows, so binary search for the smallest x whose count is at least k. That smallest value is always an entry of the matrix. Use 64-bit bounds so lo + hi cannot overflow.
- lo = matrix[0][0], hi = matrix[n-1][n-1] (as 64-bit numbers).
- While lo < hi: mid = lo + (hi - lo) / 2; count entries <= mid with the staircase walk.
- If count >= k, set hi = mid; otherwise lo = mid + 1.
- Return lo.
class Solution {
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;
if (countAtMost(matrix, mid) >= k) hi = mid;
else lo = mid + 1;
}
return (int) lo;
}
private int countAtMost(int[][] matrix, long x) {
int n = matrix.length;
int row = n - 1, col = 0, count = 0;
while (row >= 0 && col < n) {
if (matrix[row][col] <= x) {
count += row + 1;
col++;
} else {
row--;
}
}
return count;
}
}class Solution:
def kthSmallest(self, matrix: List[List[int]], k: int) -> int:
n = len(matrix)
def count_at_most(x: int) -> int:
row, col, count = n - 1, 0, 0
while row >= 0 and col < n:
if matrix[row][col] <= x:
count += row + 1
col += 1
else:
row -= 1
return count
lo, hi = matrix[0][0], matrix[n - 1][n - 1]
while lo < hi:
mid = (lo + hi) // 2
if count_at_most(mid) >= k:
hi = mid
else:
lo = mid + 1
return loclass Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
int n = matrix.size();
long long lo = matrix[0][0], hi = matrix[n - 1][n - 1];
while (lo < hi) {
long long mid = lo + (hi - lo) / 2;
if (countAtMost(matrix, mid) >= k) hi = mid;
else lo = mid + 1;
}
return (int) lo;
}
private:
int countAtMost(vector<vector<int>>& matrix, long long x) {
int n = matrix.size();
int row = n - 1, col = 0, count = 0;
while (row >= 0 && col < n) {
if (matrix[row][col] <= x) {
count += row + 1;
col++;
} else {
row--;
}
}
return count;
}
};function kthSmallest(matrix, k) {
const n = matrix.length;
const countAtMost = (x) => {
let row = n - 1, col = 0, count = 0;
while (row >= 0 && col < n) {
if (matrix[row][col] <= x) {
count += row + 1;
col++;
} else {
row--;
}
}
return count;
};
let lo = matrix[0][0], hi = matrix[n - 1][n - 1];
while (lo < hi) {
const mid = lo + Math.floor((hi - lo) / 2);
if (countAtMost(mid) >= k) hi = mid;
else lo = mid + 1;
}
return lo;
}Edge cases to test
- A 1 x 1 matrix
- k = 1 (top-left corner) or k = n² (bottom-right corner)
- Many duplicates, or every value equal
- Values near -10^9 and 10^9, where (lo + hi) overflows a 32-bit int
Hints
Hint 1
The rows are sorted lists. How would you merge n sorted lists and stop after k values?
Hint 2
Instead of searching for a position, search over values: for a guess x, how many entries are <= x?
Hint 3
Counting entries <= x takes O(n) with a staircase walk from the bottom-left corner. Binary search for the smallest x whose count is at least k.
FAQ
What is the best time complexity for Kth Smallest Element in a Sorted Matrix?
Optimal (binary search on the value) runs in O(n log R) time and O(1) extra space. Each count is O(n) (at most 2n steps), and the binary search runs about log2(2 * 10^9) ≈ 31 times, where R is the value range.
Which pattern does Kth Smallest Element in a Sorted Matrix use?
It is a binary search problem that uses the binary search on answer space pattern. Other problems with the same pattern: Koko Eating Bananas, Minimum Number of Days to Make m Bouquets, Separate Squares I.
Is there a brute force solution for Kth Smallest Element in a Sorted Matrix?
Yes. Brute force (flatten and sort) takes O(n² log n) time and O(n²) space. Copy all n² values into one array, sort it, and return the element at index k - 1.
Which edge cases should I test for Kth Smallest Element in a Sorted Matrix?
A 1 x 1 matrix; k = 1 (top-left corner) or k = n² (bottom-right corner); Many duplicates, or every value equal; Values near -10^9 and 10^9, where (lo + hi) overflows a 32-bit int.