Kth Smallest Element in a Sorted Matrix
Medium · Heap & Counting · Array · Binary Search · Sorting · Heap (Priority Queue) · Matrix
Problem
You are given an n × n integer matrix in which every row and every column is sorted in non-decreasing order, and an integer k.
Return the k-th smallest value in the matrix. Duplicates count as separate entries: the answer is the k-th element of the sorted list of all n² values, not the k-th distinct value.
Try to use less than O(n²) extra memory.
Examples
Input: matrix = [[2,4,9],[3,7,11],[6,8,15]], k = 5 Output: 7
Sorted, the values are 2, 3, 4, 6, 7, 8, 9, 11, 15, and the fifth is 7.
Input: matrix = [[1,1],[1,5]], k = 3 Output: 1
The sorted list is 1, 1, 1, 5; the third value is 1.
Input: matrix = [[-4]], k = 1 Output: -4
The only value is the answer.
Constraints
- n == len(matrix) == len(matrix[i])
- 1 <= n <= 300
- -10^9 <= matrix[i][j] <= 10^9
- Every row and every column is sorted in non-decreasing order
- 1 <= k <= n²
Approaches
- Baseline: sort every value — time O(n² log n), space O(n²)
Follow-up
A min-heap seeded with the first cell of each row, popped k times, is another standard answer: O(k log n) time and O(n) space, better when k is small. The binary search is O(n log(max - min)) and does not depend on k. The use cases apply the same "count values <= x" search to pair sums and to a multiplication table.
Related problems
Start free on Cariara · Coding problems · System design studio
