Introduction

Finding the kth smallest value in a matrix looks simple if you flatten everything and sort it, but that throws away the structure the problem gives you. In this problem, every row and every column is already sorted, which lets you do much better than a full sort. Two common solutions are a value-range binary search and a min-heap.

Why The Matrix Ordering Matters

The matrix is not globally sorted from left to right, top to bottom, but it has a very useful partial order. The smallest element is always in the top-left corner, and values grow as you move right or down.

For example:

1[
2  [1,  5,  9],
3  [10, 11, 13],
4  [12, 13, 15]
5]

If k = 8, the answer is 13.

That structure means you can count how many values are less than or equal to a candidate number without examining every element in the slowest possible way.

Binary Search On The Value Range

The most efficient general approach is to binary search between the smallest and largest matrix values. For each midpoint, count how many numbers are less than or equal to it. If that count is smaller than k, the answer must be larger. Otherwise, the answer is at that midpoint or below it.

The counting step can be done in O(n) for an n x n matrix by starting in the bottom-left corner:

1def kth_smallest(matrix, k):
2    n = len(matrix)
3    low = matrix[0][0]
4    high = matrix[-1][-1]
5
6    def count_less_equal(target):
7        row = n - 1
8        col = 0
9        count = 0
10
11        while row >= 0 and col < n:
12            if matrix[row][col] <= target:
13                count += row + 1
14                col += 1
15            else:
16                row -= 1
17
18        return count
19
20    while low < high:
21        mid = (low + high) // 2
22        if count_less_equal(mid) < k:
23            low = mid + 1
24        else:
25            high = mid
26
27    return low
28
29
30matrix = [
31    [1, 5, 9],
32    [10, 11, 13],
33    [12, 13, 15],
34]
35
36print(kth_smallest(matrix, 8))

This prints:

13

The important detail is that binary search is not happening on positions. It is happening on the value range from matrix[0][0] to matrix[-1][-1].

Heap-Based Alternative

A min-heap is another solid option, especially when k is small compared with the total number of elements. You push the first value from each row into the heap, then pop the smallest item k times while pushing the next item from the same row.

1import heapq
2
3
4def kth_smallest_heap(matrix, k):
5    n = len(matrix)
6    heap = []
7
8    for row in range(min(n, k)):
9        heapq.heappush(heap, (matrix[row][0], row, 0))
10
11    for _ in range(k - 1):
12        value, row, col = heapq.heappop(heap)
13        if col + 1 < len(matrix[row]):
14            heapq.heappush(heap, (matrix[row][col + 1], row, col + 1))
15
16    return heapq.heappop(heap)[0]
17
18
19print(kth_smallest_heap(matrix, 8))

This version is easy to reason about and runs in O(k log n) time with O(n) heap space.

Choosing Between The Two Approaches

The binary-search solution is usually the best default for square matrices because it scales well and does not depend on k being small. The heap solution is easier to explain in an interview and can be very competitive when you only need the first few smallest values.

If the matrix dimensions are rectangular instead of square, both ideas still work with small adjustments. The counting function just needs to use the true row and column sizes.

Common Pitfalls

One frequent bug is treating the matrix as if it were fully sorted in row-major order. It is not. A value on the next row can be smaller than a value later in the current row.

Another mistake is implementing binary search over indices instead of values. That breaks the logic, because the partial ordering only helps with value comparisons.

Duplicates also matter. The counting function must count values less than or equal to the midpoint, not strictly less than it. Using the wrong comparison often produces off-by-one errors when duplicates are present.

Finally, be careful with the heap approach if rows have different lengths. The example above assumes each pushed item can safely advance within its own row.

Summary

• Use the sorted rows and columns instead of flattening the matrix.
• Binary search on the value range gives an efficient general solution.
• Count values less than or equal to a midpoint in linear time per search step.
• A min-heap is a clean alternative when k is relatively small.
• Handle duplicates carefully to avoid off-by-one errors.