Kth Smallest Element in a Sorted Matrix — Problem & Solution
Kth Smallest Element in a Sorted Matrix solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Kth Smallest Element in a Sorted Matrix is a medium coding problem on arrays, sorting and binary search, asked in Amazon, Google, Meta and Uber interviews.
- Difficulty: Medium
- Topics: Arrays, Sorting, Binary Search, Matrix, Heap
- Asked at: Amazon, Google, Meta, Uber, Twitter, PhonePe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given an n × n matrix where each row and each column is sorted in ascending order, return the k-th smallest element in the matrix.
Note this is the k-th smallest in sorted order, counting duplicates separately — not the k-th distinct value.
Example 1
Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: Sorted, the matrix reads 1,5,9,10,11,12,13,13,15.
Example 2
Input: matrix = [[-5]], k = 1
Output: -5
Example 3
Input: matrix = [[1,2],[1,3]], k = 2
Output: 1
Constraints
1 <= matrix.length <= 8matrix[i].length == matrix.length-1000 <= matrix[i][j] <= 10001 <= k <= n²
Follow-up: Flattening and sorting is O(n² log n). Can you do it in O(n log(max - min)) using binary search on the answer?
Hints for Kth Smallest Element in a Sorted Matrix
Hint 1
Flattening and sorting is correct and simple — start there.
Hint 2
A min-heap seeded with the first column pops the smallest element
ktimes in O(k log n).Hint 3
Best: binary search on the value, counting how many entries are at most the midpoint using the row/column sortedness.
How to solve Kth Smallest Element in a Sorted Matrix
Flatten and sort, then index k - 1.
Approach
- Collect all
n²values. - Sort and return the
(k-1)-th.
Why it works
The k-th smallest counting duplicates is by definition position k - 1 in the sorted multiset.
Complexity
- Time —
O(n² log n) - Space —
O(n²)
Pitfalls
- A min-heap seeded with the first column pops
ktimes inO(k log n); binary search on the value with a staircase count isO(n log(range)).
Reference solution
Python
def kthSmallest(matrix, k: int) -> int:
flat = [v for row in matrix for v in row]
flat.sort()
return flat[k - 1]Java
public static int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
int[] flat = new int[n * n];
int idx = 0;
for (int[] row : matrix) {
for (int v : row) flat[idx++] = v;
}
Arrays.sort(flat);
return flat[k - 1];
}C++
int kthSmallest(vector<vector<int>>& matrix, int k) {
vector<int> flat;
for (const auto& row : matrix) {
for (int v : row) flat.push_back(v);
}
sort(flat.begin(), flat.end());
return flat[k - 1];
}JavaScript
var kthSmallest = function(matrix, k) {
const flat = [];
for (let r = 0; r < matrix.length; r++) {
for (let c = 0; c < matrix[r].length; c++) flat.push(matrix[r][c]);
}
flat.sort(function(a, b) { return a - b; });
return flat[k - 1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms