Kth Smallest Element in a Sorted Matrix
Maintained by Vikas D, software engineer
You receive an n by n matrix. Both directions are sorted: scanning left to right across any row gives non-decreasing values, and scanning top to bottom down any column does the same. There is no single global sorted line through the grid, only this row and column structure.
Picture flattening every cell into one long ascending list. Your job is to return the element that lands in position k of that list, counting from 1. Duplicate values keep their slots, so if the same number appears several times it is counted each time rather than collapsed to one.
The diagonal sorting means the smallest value is always the top-left cell and the largest is always the bottom-right, but the ordering of everything in between is not obvious. A value high up in a later column can be smaller than a value low down in an earlier column, which is what makes the rank lookup interesting.
Return the single integer at rank k. The matrix can hold negative numbers, and k is guaranteed to be a valid rank between 1 and n squared.
Examples
Sorted in full the entries are 1,5,9,10,11,12,13,13,15. The 8th value in that order is 13 (the first of the two 13s), so duplicates are counted by position not by distinctness.
Sorted order is 1,3,5,6,7,11,12,14,14. Counting to position 5 gives 7. Note 11 in row 3 is smaller than 12 in row 2, so column order alone does not predict the rank.
A single-cell grid has exactly one element, which is both the minimum and the only rank available.
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^2
Visible test cases
- kthSmallest([[1,5,9],[10,11,13],[12,13,15]], 8) == 13
- kthSmallest([[-5]], 1) == -5
- kthSmallest([[1,2],[3,4]], 2) == 2
- kthSmallest([[1,2],[3,4]], 3) == 3
- kthSmallest([[1,3,5],[6,7,12],[11,14,14]], 5) == 7
- kthSmallest([[1,2,3],[4,5,6],[7,8,9]], 1) == 1
Hints
Hint 1
Each row is already sorted, so this is close to merging n sorted lists and stopping at the k-th item rather than producing the whole merge.
Hint 2
A min-heap can track the current front of each row. Pop the smallest, then push the next cell from that same row so the heap always holds at most one candidate per started row.
Hint 3
If you want to beat the heap on memory, notice that for any candidate value v you can count how many entries are <= v in O(n) by walking from the bottom-left corner. That count is monotonic in v, which invites binary search on the value range.
Approaches
Flatten and sort
Time O(n^2 log n) · Space O(n^2)Ignore the sorted structure entirely, collect every cell into one array, sort it, and index into rank k.
- Spread all n*n entries into a single flat list.
- Sort the list in ascending order.
- Return the element at index k-1.
Min-heap k-way merge
Time O(k log n) · Space O(n)Treat the rows as sorted lists and merge them lazily with a min-heap, advancing only as far as rank k. The heap never holds more than one in-progress entry per row.
- Seed a min-heap with the first cell of each of the first min(n, k) rows, storing value plus its row and column index.
- Pop the smallest entry k times; the value popped on the k-th pop is the answer.
- After each pop, if the popped cell has a right neighbour in its row, push that neighbour so the row keeps contributing its next-smallest value.
Binary search on value
Time O(n log(maxVal - minVal)) · Space O(1)Search the numeric range from the top-left minimum to the bottom-right maximum. For a midpoint value, count entries less than or equal to it in linear time using the staircase from the bottom-left corner, and narrow the range until the smallest value with count >= k is found.
- Set lo to matrix[0][0] and hi to matrix[n-1][n-1].
- While lo < hi, take mid, then walk from the bottom-left: move up when the cell exceeds mid, otherwise add the column height and move right to tally how many entries are <= mid.
- If that count is at least k, set hi = mid, else set lo = mid + 1; when the range collapses, lo is the k-th smallest because it is the smallest value whose count reaches k.
Common mistakes
- Counting distinct values instead of positions. Rank k counts duplicates, so two equal entries occupy two ranks, not one.
- Seeding the heap with every row when k is small. Capping the initial push at min(n, k) rows avoids touching rows that can never reach rank k.
- Off-by-one on the rank. The answer is the value popped on the k-th pop (1-indexed), not after k+1 pops or at array index k.
- In the binary-search variant, returning mid when the count first reaches k. The correct answer is the converged lo, since mid itself may not be an actual matrix value.
- Comparing on the wrong heap key. The heap must order by the cell value, not by row or column index, or it will pop in the wrong order.
Follow-up variations
- Solve it when the matrix is n by m and not square, so rows and columns differ in length.
- Return the row and column coordinates of the k-th smallest, not just its value.
- Handle a streaming or very large matrix where you cannot hold n^2 values in memory and must keep space sublinear.
- Find the k-th largest instead, and discuss whether you mirror the heap or adjust the binary-search count.
- Support repeated queries for many different k values on the same matrix more efficiently than answering each from scratch.