Kth Smallest Element in a Sorted Matrix (LeetCode 378): Binary Search on Value Space

You have a sorted matrix and you need to find its kth smallest element. This is LeetCode 378: Kth Smallest Element in a Sorted Matrix, and the trick that makes it elegant is searching the value space rather than the index space.

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: it is the kth smallest in sorted order, not the kth distinct element. Duplicate values can appear, and you count every occurrence.

Example:

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

The 8th smallest is 13. If you flatten and sort: [1, 5, 9, 10, 11, 12, 13, 13, 15], the element at index 7 (1-indexed: 8) is 13.

Why a naive approach falls short

The brute-force path is to flatten the matrix, sort it, and index into it. That works in O(n^2 log n) time and O(n^2) space. You can do better.

A heap-based approach is another natural choice: use a min-heap to merge the rows (like merging sorted arrays). That runs in O(k log n), which is fine when k is small but gets expensive when k is close to n^2.

The cleanest solution runs in O(n log(max - min)) time and O(1) extra space. It uses binary search -- not on indices, but on the answer value itself.

val <= mid (8)answer (k=8 -> 13)val > mid

The key insight: search on value, not index

The matrix has two useful properties:

1. Each row is sorted left to right.
2. Each column is sorted top to bottom.

These properties let you efficiently count how many elements are <= some value mid. And if you can count quickly, you can binary search on the answer.

Here is the plan:

• Set lo = matrix[0][0] (the minimum) and hi = matrix[n-1][n-1] (the maximum).
• For each mid = (lo + hi) // 2, count how many elements in the matrix are <= mid.
• If that count is >= k, the kth smallest is somewhere in [lo, mid], so set hi = mid.
• Otherwise, set lo = mid + 1.
• When lo == hi, you have your answer.

One subtlety: the value mid might not even exist in the matrix. But that is fine. When count >= k, you set hi = mid. This pushes hi down toward an actual value. When lo == hi, the value is guaranteed to exist in the matrix because at every convergence point, lo is always a value that was "just enough" to include k elements.

Counting elements with a two-pointer walk

The clever part is the count function. You could scan the entire matrix naively in O(n^2), but you can do it in O(n) using the sorted structure.

Start at the bottom-left corner: row = n-1, col = 0.

• If matrix[row][col] <= mid: everything in column col from row 0 to row row is also <= mid (since the column is sorted). That is row + 1 elements. Move col right.
• Otherwise: matrix[row][col] is too large. Move row up.

You keep walking until you go out of bounds. This is an O(n) traversal.

Python solution

def kthSmallest(matrix, k):
    n = len(matrix)
    lo, hi = matrix[0][0], matrix[n - 1][n - 1]

    def count_lte(mid):
        count = 0
        row, col = n - 1, 0
        while row >= 0 and col < n:
            if matrix[row][col] <= mid:
                count += row + 1
                col += 1
            else:
                row -= 1
        return count

    while lo < hi:
        mid = lo + (hi - lo) // 2
        if count_lte(mid) >= k:
            hi = mid
        else:
            lo = mid + 1

    return lo

Walk through the logic:

• lo + (hi - lo) // 2 avoids overflow (though in Python integers are unbounded, it is a good habit).
• count_lte starts at the bottom-left and walks right when a cell qualifies, up when it does not.
• The binary search loop terminates because every iteration strictly narrows the range: either hi decreases or lo increases.
• When lo == hi, return lo. It is always a value that exists in the matrix.

Complexity

The binary search runs log(max - min) iterations. Each iteration calls count_lte, which walks at most 2n steps (at most n right-moves and n up-moves). So total time is O(n log(max - min)).

For an n x n matrix where values fit in a 32-bit integer, log(max - min) is at most around 30. That makes the practical runtime very fast.

Space is O(1): you only use a few pointers and counters, no auxiliary data structures.

Building blocks

Binary search on value space

Most binary search problems search an index space: "find the position where condition changes." Here you search the value space: "find the smallest value for which count >= k." The template is:

lo, hi = min_possible, max_possible
while lo < hi:
    mid = lo + (hi - lo) // 2
    if feasible(mid):
        hi = mid
    else:
        lo = mid + 1
return lo

This pattern appears in problems like Koko Eating Bananas, Capacity to Ship Packages, and Split Array Largest Sum. The key question is always: "can I define a monotone predicate on values?" Here the predicate is count_lte(mid) >= k.

Two-pointer count in a sorted matrix

The bottom-left walk is a building block in its own right. It lets you answer "how many elements satisfy condition X?" in O(n) for any matrix sorted along rows and columns. The same walk appears in Search a 2D Matrix II, where instead of counting you are looking for an exact value.

The invariant: at any point (row, col), every element in rows 0 through row in column col-1 (and earlier columns) has already been counted.

Edge cases

• k = 1: lo starts at matrix[0][0] and count_lte(lo) >= 1 immediately, so hi = lo and you return matrix[0][0]. Correct.
• k = n*n: hi starts at matrix[n-1][n-1] and the count always equals n*n, so hi = lo converges to the maximum. Correct.
• 1x1 matrix: lo == hi from the start, the while loop never runs, and you return lo = matrix[0][0]. Correct.
• Duplicate values: The count function counts all occurrences, so duplicates are handled naturally. The final lo is the actual kth element including duplicates.

From understanding to recall

Understanding this solution once is not the same as being able to write it under pressure. The parts that tend to slip:

• Why hi = mid (not hi = mid - 1) when count >= k. Setting hi = mid - 1 could skip the actual answer.
• The direction of the two-pointer walk. You start at the bottom-left, not the top-right, because moving right keeps you in the counted region while moving up excludes elements.
• Why return lo and not return hi at the end. They are equal when the loop exits, so it does not matter -- but knowing why they converge to the same valid matrix value helps you trust the result.

Spaced repetition targets exactly these details. You write the solution from scratch, not by recognizing a blog post, but by reconstructing it from the invariants. A few sessions spaced a day apart, then a week, and the pattern becomes durable.

CodeBricks breaks this problem into separate drills: the binary search skeleton, the count_lte function, and the full solution. Each building block gets its own repetition schedule so the details stick independently.

Related posts

• Kth Largest Element - Same "kth" framing but solved with a heap or quickselect on a flat array
• Find K Pairs with Smallest Sums - Another problem where the kth smallest comes from a sorted 2D structure, solved with a heap
• Binary Search Pattern - The core template that powers the value-space search here