Kth Smallest in a Sorted Matrix: The Min-Heap k-Way Merge
Solve Kth Smallest Element in a Sorted Matrix with a min-heap of frontier cells — intuition, JavaScript code, a worked walkthrough, and complexity.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
A matrix where every row is sorted and every column is sorted looks like it should be trivial to search — but the whole thing is not globally sorted. The largest element of row 0 can be smaller than the first element of row 2. So finding the kth smallest value hides a real question: how do you walk a partially-ordered grid in increasing order without materializing all n² cells?
The answer is one of the most reusable ideas in interview prep: a min-heap that tracks only the frontier. Instead of sorting everything, you keep a tiny set of "next candidates" and repeatedly pull the global minimum from it. That's the same k-way merge machinery behind merging sorted lists, and it's exactly what the visualizer for this problem animates.
The problem
Given an n x n matrix where each row and each column is sorted in ascending order, return the kth smallest element in the matrix. Note this is the kth smallest in sorted value order — counting duplicates — not the kth distinct value.
Input: matrix = [[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]], k = 8
Output: 13
// Flatten + sort → 1,5,9,10,11,12,13,13,15
// The 8th value in that order is 13 (the second 13).Two facts shape everything that follows:
- Rows are sorted, so within any row the next-smallest unseen value is always the cell immediately to the right of the last one you took.
- The matrix is not globally sorted, so you can't binary-search positions directly — you have to merge rows.
The brute force baseline
The naive move ignores the structure entirely: copy all n² cells into one array, sort it, and index position k-1.
function kthSmallest(matrix, k) {
const flat = [];
for (const row of matrix) {
for (const val of row) flat.push(val);
}
flat.sort((a, b) => a - b);
return flat[k - 1];
}This is correct and easy, but it throws away the sortedness you were handed. Sorting n² elements costs O(n² log n) time and O(n²) extra space. For a 1000×1000 matrix that's a million elements sorted just to read one of them. An interviewer will nod, then ask you to use the fact that the rows are already sorted.
The key insight: merge rows with a frontier heap
Think of each row as an already-sorted stream. Finding the kth smallest across all rows is a k-way merge — the same problem as merging n sorted lists and stopping after k outputs.
You never need all n streams fully expanded at once. You only need the current smallest unseen cell from each row — the frontier. A min-heap gives you the global minimum of that frontier in O(log n), and when you consume a cell, its replacement is simply the next cell to its right in the same row.
So the loop is:
- Seed the heap with the first column — one entry per row,
{val, row, col: 0}. - Pop the minimum. That's the next-smallest value globally.
- Push the popped cell's right neighbor (if the row hasn't ended), because that's now this row's frontier.
- Repeat the pop-then-push exactly
k - 1times. After those pops, the heap's root is the kth smallest.
The heap never holds more than n entries — one live frontier cell per row.
The optimal solution
This mirrors the exact algorithm the visualizer steps through. Each heap entry carries its coordinates so that after popping we know which right-neighbor to feed back in.
var kthSmallest = function (matrix, k) {
let n = matrix[0].length;
let heap = new MinPriorityQueue(x => x.val);
// Seed the first column: one frontier cell per row.
for (let i = 0; i < Math.min(n, k); i++) {
heap.push({ val: matrix[i][0], row: i, col: 0 });
}
// Pop the global minimum k-1 times, advancing each row's frontier.
for (let count = 0; count < k - 1; count++) {
let { val, row, col } = heap.pop();
if (col + 1 < n) {
heap.push({ val: matrix[row][col + 1], row, col: col + 1 });
}
}
return heap.pop().val;
};Two details worth pausing on:
- Seeding
Math.min(n, k)rows, not all n. Ifkis smaller than the number of rows, you can never reach rows below index k — the kth smallest is decided long before them. Seeding fewer rows saves heap operations. - The
col + 1 < nguard. When a row's frontier hits the right edge there is no neighbor to push. You simply skip the push; the other rows keep feeding the heap.
After k - 1 pops, every value strictly smaller than the answer has already been popped, so the current heap root is exactly the kth smallest — one final pop() returns it.
Walkthrough
Trace matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 5. Here n = 3, so we seed all three rows, then perform k - 1 = 4 pops. The answer should be the 5th smallest: 1,5,9,10,11.
| Step | Action | Popped {val,row,col} | Push (right neighbor) | Heap after (vals) |
|---|---|---|---|---|
| Seed | push col 0 of rows 0,1,2 | — | 1, 10, 12 | 1, 10, 12 |
| Pop 1 | pop min | {1,0,0} | matrix[0][1] = 5 | 5, 10, 12 |
| Pop 2 | pop min | {5,0,1} | matrix[0][2] = 9 | 9, 10, 12 |
| Pop 3 | pop min | {9,0,2} | col+1 = 3, row exhausted | 10, 12 |
| Pop 4 | pop min | {10,1,0} | matrix[1][1] = 11 | 11, 12 |
| Return | root of heap | — | — | 11 |
Pop 3 is the instructive one: row 0's frontier reached column 2 (col + 1 == n), so there is nothing to push and the heap shrinks. The merge keeps flowing from the remaining rows. After four pops, the root is 11 — the 5th smallest, exactly as predicted.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Flatten + sort | O(n² log n) | O(n²) | sorts every cell to read one |
| Min-heap frontier merge | O(k log n) | O(n) | k pops/pushes, heap capped at n entries |
| Binary search on value | O(n log(max−min)) | O(1) | count ≤ mid per candidate value |
The heap version does at most k - 1 pops and pushes, each costing O(log n) because the heap holds at most n frontier cells. Seeding is O(n). Total time is O(k log n), space O(n). When k is close to n², a binary search on the value range can win, but the heap is the clean, interview-ready default and the one the visualizer teaches.
Common mistakes
- Flattening and sorting. It works but discards the sorted structure — O(n² log n) when O(k log n) is on the table. State it as a baseline, then beat it.
- Pushing the cell below instead of to the right. Advancing down a column double-counts values, because every column entry after the first is already reachable as some row's right-neighbor. Advance right only; columns take care of themselves.
- Forgetting the
col + 1 < nbound. Readingmatrix[row][n]isundefined; pushing it corrupts the heap. Guard the right edge. - Looping k times instead of k-1. You pop
k - 1values away, then read the root. An extra pop returns the (k+1)th smallest. - Seeding rows but using
kheap capacity blindly. Seedmin(n, k)rows — seeding more wastes work and, if you mis-bound the loop, can index past the matrix.
Where this pattern shows up next
The frontier-heap idea generalizes to any "pull the next-smallest across many sorted sources" problem:
- Min-Heap Operations — the underlying data structure: how push and pop keep the minimum at the root in O(log n).
- Kth Largest Element in an Array — the mirror image, using a bounded heap to hold the top-k.
- Kth Largest Element in a Stream — a size-k min-heap that answers the kth-largest query as values arrive one at a time.
- Top K Frequent Elements — count with a hash map, then rank the top k with a heap.
You can also step through the algorithm interactively to watch the frontier heap seed, pop, and push cell by cell.
FAQ
Why use a min-heap instead of just sorting the matrix?
Sorting flattens all n² cells and costs O(n² log n), throwing away the sorted rows you were given. A min-heap does a k-way merge: it holds only the frontier — one candidate per row, at most n entries — and pulls the global minimum in O(log n). You stop after k pops, so the total work is O(k log n), which is far less than sorting when k is small relative to n².
What exactly goes into the heap?
Each heap entry is an object {val, row, col}, ordered by val. The coordinates are essential: when you pop the minimum, you need to know which cell it was so you can push its right neighbor matrix[row][col + 1] as that row's new frontier. Storing just the value would leave you unable to advance the correct row.
Why do we pop k-1 times and then read the root?
Each pop removes one value in ascending order — the 1st smallest, 2nd smallest, and so on. After k - 1 pops, every value strictly less than the answer has been removed, so the smallest value still in the heap (its root) is the kth smallest. A final heap.pop() returns it. Popping k times instead would hand back the (k+1)th smallest.
When is binary search better than the heap?
Binary-search-on-value runs in O(n log(max − min)) with O(1) space: guess a value mid, count how many matrix elements are ≤ mid in O(n) by walking from the bottom-left corner, then shrink the range. It doesn't depend on k, so when k approaches n² it beats the heap's O(k log n). For typical interview inputs and clarity, the min-heap frontier merge is the recommended solution.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.