Kth Smallest in a Sorted Matrix — Heap or Binary Search Answer

Problem Statement#

Given an n x n matrix where each row and column is sorted in ascending order, return the k-th smallest element in the matrix.

Constraints:

• 1 <= n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• 1 <= k <= n^2

Input:  matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13

Input:  matrix = [[-5]], k = 1
Output: -5

Why This Problem Matters#

This is a heap FAANG classic that lets the interviewer probe two skills at once: priority queue mechanics and binary search on the answer space. Google and Amazon use it to separate candidates who blindly flatten and sort from those who exploit the row-column ordering.

It also generalizes to "k-th smallest sum of pairs" and selection in two-dimensional structures, so the technique is reusable.

The Core Insight#

Two valid optimal-class solutions exist:

1. Min-heap k-way merge — start from the first row (or first column) and pop k times, pushing the cell directly below each popped item.
2. Binary search on the value range — count cells less than or equal to a candidate value using the staircase method in O(n).

The heap is intuitive; the binary search is asymptotically better when k approaches n^2.

Visual Dry Run#

For [[1,5,9],[10,11,13],[12,13,15]], k = 8:

Solution (Optimal)#

import heapq
 
class Solution:
    def kthSmallest(self, matrix, k):
        n = len(matrix)
        heap = [(matrix[r][0], r, 0) for r in range(min(k, n))]
        heapq.heapify(heap)
        for _ in range(k - 1):
            val, r, c = heapq.heappop(heap)
            if c + 1 < n:
                heapq.heappush(heap, (matrix[r][c + 1], r, c + 1))
        return heap[0][0]

var kthSmallest = function(matrix, k) {
    const n = matrix.length;
    const heap = new MinHeap((a, b) => a[0] - b[0]);
    for (let r = 0; r < Math.min(k, n); r++) heap.push([matrix[r][0], r, 0]);
    for (let i = 0; i < k - 1; i++) {
        const [, r, c] = heap.pop();
        if (c + 1 < n) heap.push([matrix[r][c + 1], r, c + 1]);
    }
    return heap.top()[0];
};

Time: O(k log min(k, n)) — heap stays bounded by min(k, n). Space: O(min(k, n)) — heap entries.

Common Mistakes#

• Flattening the matrix and sorting — O(n^2 log n) and ignores structure
• Pushing every cell into the heap — wasteful when k is small
• Forgetting that columns are also sorted — so the min-heap can seed with rows or columns
• Using a max-heap of size k — works but is slower when k > n^2 / 2
• Off-by-one when k = 1 — the heap top is the answer immediately

Interview Tips#

• Always offer both the heap and binary search solutions; let the interviewer pick
• Explain why seeding only the first column (or row) is enough — column k can never appear before column k-1
• For binary search, explain the staircase counter that walks from bottom-left in O(n)
• Mention the trade-off: heap is simpler; binary search is O(n log(max - min)) which beats heap when k is big

Follow-up Questions#

• What if rows and columns are not equal length? Same heap approach
• Find k-th largest? Reverse the comparator or seed from the bottom row
• The matrix is sorted only by rows? Use a different strategy — heap of all row heads
• k-th smallest sum of pairs? See LeetCode 373 — same heap idea
• Streaming matrix where new cells arrive? Maintain a top-k heap

Key Takeaways#

• Two optimal approaches: heap k-way merge or binary search on value range
• Heap solution is O(k log min(k, n)) and easy to explain
• Binary search uses a staircase counter — beats heap when k is near n^2
• Seed only one row or column to keep the heap size bounded
• Tuple ordering (value, row, col) makes Python's heapq deterministic
• Pattern reused in k-th smallest pair sum, selection in BSTs, and external sort
• Heap FAANG must-know — memorize both approaches