Kth Smallest Element in a Sorted Matrix — Binary Search on Value [LC 378, Google]

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:

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -10^9 <= matrix[i][j] <= 10^9
• All rows and columns are sorted in non-decreasing order
• 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#

LC 378 is a Google interview staple that combines binary search on value with an efficient matrix counting technique. The matrix is NOT globally sorted (unlike LC 74), so the flat-index trick does not apply here. Instead, binary search on the value range [matrix[0][0], matrix[n-1][n-1]] and count elements at each midpoint.

The counting step — using a staircase walk from the bottom-left corner — is itself a classic technique. It runs in O(n) and is the same logic used in LC 240 (Search a 2D Matrix II). Combining O(n) counting with O(log(max - min)) binary search gives O(n log V) where V is the value range, which outperforms heap-based approaches (O(k log n)) for large k.

The Core Insight#

Binary search on the answer value, not the matrix index. For a guessed value mid:

• Count the number of elements <= mid using a staircase walk: start at bottom-left, move right when matrix[r][c] <= mid (add the entire column above, r + 1 elements), move up when matrix[r][c] > mid.
• If count >= k, the kth smallest is at most mid — try lower (hi = mid).
• If count < k, the kth smallest is greater than mid — try higher (lo = mid + 1).
• The loop converges to the exact kth smallest value, which is guaranteed to exist in the matrix.

Visual Dry Run#

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

Search range: lo = 1, hi = 15

Solution (Optimal)#

class Solution:
    def kthSmallest(self, matrix: list[list[int]], k: int) -> int:
        n = len(matrix)
 
        def count_le(mid: int) -> int:
            # Staircase walk: start bottom-left, count elements <= mid
            count = 0
            r, c = n - 1, 0
            while r >= 0 and c < n:
                if matrix[r][c] <= mid:
                    count += r + 1  # all elements in column c, rows 0..r are <= mid
                    c += 1
                else:
                    r -= 1
            return count
 
        lo, hi = matrix[0][0], matrix[n - 1][n - 1]
        while lo < hi:
            mid = lo + (hi - lo) // 2
            if count_le(mid) >= k:
                hi = mid
            else:
                lo = mid + 1
        return lo

var kthSmallest = function(matrix, k) {
    const n = matrix.length;
 
    function countLE(mid) {
        let count = 0;
        let r = n - 1, c = 0;
        while (r >= 0 && c < n) {
            if (matrix[r][c] <= mid) {
                count += r + 1;
                c++;
            } else {
                r--;
            }
        }
        return count;
    }
 
    let lo = matrix[0][0];
    let hi = matrix[n - 1][n - 1];
 
    while (lo < hi) {
        const mid = lo + Math.floor((hi - lo) / 2);
        if (countLE(mid) >= k) hi = mid;
        else lo = mid + 1;
    }
 
    return lo;
};

Time: O(n log(max - min)) — O(log V) binary search iterations, each O(n) staircase count Space: O(1) — only pointer variables

Common Mistakes#

• Using a heap-based approach: it works (O(k log n)) but is not the expected O(n log V) solution at FAANG interviews.
• Trying to apply the flat-index binary search from LC 74 — this matrix is NOT globally sorted, so flat indexing gives wrong element order.
• Using O(n^2) counting (scanning the entire matrix for each mid) — the staircase trick makes it O(n).
• Not realising the final lo is guaranteed to exist in the matrix — the convergence property of this search ensures lo is always a matrix value.
• Starting the staircase from the top-right instead of bottom-left — both work, but choose one and be consistent.

Interview Tips#

• Clarify that this is NOT LC 74 — the matrix is only row-sorted and column-sorted, not globally sorted.
• Draw the staircase walk explicitly when explaining the counting function — it takes 30 seconds but prevents confusion.
• Mention both the heap approach (O(k log n)) and the binary search approach (O(n log V)), and explain when each is preferred.
• The binary search converges to a value that exists in the matrix — this is not obvious but is provable from the counting function's properties.

Follow-up Questions#

• Heap approach: Use a min-heap initialised with the first column. Pop k times, pushing the element to the right each time. O(k log n), good when k is small.
• LC 668 (Kth Smallest Number in Multiplication Table): Same binary search + counting approach but counting is O(n) via division.
• LC 719 (Find K-th Smallest Pair Distance): Binary search on distance with O(n log n) counting.
• What if the matrix is 1D sorted? Use standard order-statistics or the quickselect algorithm.
• Is the final lo always a matrix element? Yes. The counting function is monotone integer-valued, and lo converges to a value where the count crosses k — that crossover always lands on an actual matrix value.

Key Takeaways#

• LC 378 uses binary search on the value range [matrix[0][0], matrix[n-1][n-1]], not on array indices — a key mental shift from standard binary search.
• The staircase walk from bottom-left counts elements <= mid in O(n): move right when matrix[r][c] <= mid (adding r+1 elements), move up otherwise.
• Use while lo < hi with hi = mid when count >= k and lo = mid + 1 when count < k to converge on the minimum value with count >= k.
• The final lo is always a matrix element — the counting function's integer properties guarantee this convergence.
• This approach is O(n log V) where V = max - min, beating heap-based O(k log n) for large k.
• Google asks this problem to verify both the binary-search-on-value insight and knowledge of the staircase counting trick.
• This same binary search + counting framework solves LC 668 (multiplication table kth), LC 719 (kth pair distance), and LC 786 (kth smallest prime fraction).