Kth Smallest Element in a Sorted Matrix
Find the kth smallest value in a matrix whose rows and columns are sorted by merging the rows with a min-heap: pop k - 1 times, then read the top.
Problem Understanding
Kth Smallest Element in a Sorted Matrix: given an n × n matrix whose rows and columns are each sorted ascending, return the kth smallest element in sorted order (counting duplicates), using better than O(n²) memory.
Example: [[1,5,9],[10,11,13],[12,13,15]], k = 8 returns 13.
The Intuition: Merge the Rows Until the kth Value
Sorting all n² values works but wastes memory. Instead, notice that every row is already sorted:
- Treat the rows as
nsorted lists, like Merge k Sorted Lists. - Keep a min-heap with the next unread cell of each row. Its top is the smallest value not yet taken.
- Pop it, then push the next cell of the same row. After
k - 1pops the top is thekth smallest.
Only the first min(n, k) rows ever matter, which keeps the heap small. The sorted columns also allow a binary search on the value itself, the same staircase walk used in Search a 2D Matrix II.
Interactive Walkthrough
Cells waiting in the heap are tinted; popped cells fade and show their pop order. The cell just popped is solid and its right neighbour, just pushed, is outlined. Try Duplicates to see equal values counted separately.
Dry Run Table
Input: [[1,5,9],[10,11,13],[12,13,15]], k = 8. The heap starts with 1, 10, 12.
| Pop | Value (r, c) | Pushed | Heap after |
|---|---|---|---|
| 1 | 1 (0, 0) | 5 | 5, 10, 12 |
| 2 | 5 (0, 1) | 9 | 9, 10, 12 |
| 3 | 9 (0, 2) | row done | 10, 12 |
| 4 | 10 (1, 0) | 11 | 11, 12 |
| 5 | 11 (1, 1) | 13 | 12, 13 |
| 6 | 12 (2, 0) | 13 | 13, 13 |
| 7 | 13 (1, 2) | row done | 13 |
Answer: after 7 pops the top is 13 (2, 1), the 8th smallest.
The Solution Template
Heap merge in Python, Java, C++, JavaScript and TypeScript (the last two include a small binary heap). C uses the binary search on values instead, which needs no heap.
Kth Smallest Element in a Sorted Matrix Code
1var kthSmallest = function(matrix, k) {2 const n = matrix.length, heap = [];3 for (let r = 0; r < Math.min(n, k); r++) push(heap, [matrix[r][0], r, 0]);4 for (let i = 0; i < k - 1; i++) {5 const [, r, c] = pop(heap);6 if (c + 1 < n) push(heap, [matrix[r][c + 1], r, c + 1]);7 }8 return heap[0][0];9};1011// Minimal binary min-heap on [value, row, col].12function push(heap, item) {13 heap.push(item);14 let i = heap.length - 1;15 while (i > 0) {16 const p = (i - 1) >> 1;17 if (heap[p][0] <= heap[i][0]) break;18 [heap[p], heap[i]] = [heap[i], heap[p]];19 i = p;20 }21}2223function pop(heap) {24 const top = heap[0], last = heap.pop();25 if (heap.length) {26 heap[0] = last;27 let i = 0;28 while (true) {29 let m = i;30 const l = 2 * i + 1, r = l + 1;31 if (l < heap.length && heap[l][0] < heap[m][0]) m = l;32 if (r < heap.length && heap[r][0] < heap[m][0]) m = r;33 if (m === i) break;34 [heap[m], heap[i]] = [heap[i], heap[m]];35 i = m;36 }37 }38 return top;39}
Edge Cases & Common Mistakes
- k = 1: no pops; the answer is
matrix[0][0]. - k = n²: the answer is
matrix[n-1][n-1]. - Duplicates: count each cell separately;
[[1,2],[1,3]]withk = 2is1. - Seeding every cell: pushing all n² values works but uses O(n²) memory, which the problem asks you to beat.
- Binary search midpoint: with negative values,
(lo + hi) / 2rounds toward zero in C and Java;lo + (hi - lo) / 2is safe.
Summary
Merge the sorted rows with a min-heap seeded by each of the first min(n, k) rows. Pop k - 1 times, pushing each popped cell's right neighbour; the heap top is then the kth smallest. O(k log min(n, k)) time. Binary search on values is the O(1)-space alternative.
More practice: DSA interview questions with answers · patterns cheat sheet