Find the Kth Smallest Element in a Sorted Matrix Using Binary Search on Answer

Introduction

This problem asks us to find the kth smallest element in an n × n matrix where:

Each row is sorted in ascending order.
Each column is sorted in ascending order.

The challenge is to find the kth smallest element efficiently without flattening and sorting the entire matrix.

Key Idea

We do not flatten the matrix into a one-dimensional array and sort it, as that would be inefficient for large matrices.

Instead, we use a powerful technique known as:

Binary Search on Answer

Why Binary Search Works

Because the matrix is sorted both row-wise and column-wise:

Small values are located near the top-left corner.
Large values are located near the bottom-right corner.

This ordering allows us to binary search over the range of possible values instead of searching through positions.

The Strategy

For a guessed value mid, count:

How many elements are ≤ mid?

Based on that count:

If count ≥ k, the answer may be mid or a smaller value, so move left.
If count < k, the answer must be larger, so move right.

Counting Elements Efficiently

A key part of the solution is counting how many elements are less than or equal to mid.

Instead of scanning the entire matrix, we can do it in O(n) time.

Traversal Strategy

Start from the top-right corner.

For each position:

Case 1: Current Element ≤ Mid

If:

mat[row][col] ≤ mid

Then:

Every element from column 0 to col in the same row is also ≤ mid.
Add (col + 1) to the count.
Move down to the next row.

Case 2: Current Element > Mid

If:

mat[row][col] > mid

Then:

The current element and all elements below it in that column are too large.
Move left.

This allows counting in linear time relative to the matrix size.

Algorithm

Step 1: Define the Search Range

The smallest possible answer is:

mat[0][0]

The largest possible answer is:

mat[n - 1][n - 1]

Initialize:

low = mat[0][0]
high = mat[n - 1][n - 1]

Step 2: Perform Binary Search

While:

low < high

Compute:

mid = low + (high - low) / 2

Count the number of elements less than or equal to mid.

Decision

If:

count < k

Move right:

low = mid + 1

Otherwise:

high = mid

Step 3: Return the Answer

When the search ends:

low == high

This value represents the smallest number for which at least k elements are less than or equal to it.

Return:

low

Example Intuition

Suppose:

k = 7

The algorithm repeatedly narrows the search range until it finds the smallest value such that:

At least 7 elements are ≤ that value

This value is exactly the 7th smallest element.

Java Solution

class Solution {

    private int countLessEqual(int[][] mat, int mid) {
        int n = mat.length;
        int row = 0;
        int col = n - 1;
        int count = 0;

        while (row < n && col >= 0) {
            if (mat[row][col] <= mid) {
                count += (col + 1);
                row++;
            } else {
                col--;
            }
        }

        return count;
    }

    public int kthSmallest(int[][] mat, int k) {
        int n = mat.length;

        int low = mat[0][0];
        int high = mat[n - 1][n - 1];

        while (low < high) {
            int mid = low + (high - low) / 2;

            if (countLessEqual(mat, mid) < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }

        return low;
    }
}

Dry Run

Matrix

[
 [1, 5, 9],
 [10, 11, 13],
 [12, 13, 15]
]

Input

k = 8

Search Range

low = 1
high = 15

First Iteration

mid = 8

Count elements ≤ 8:

Since:

2 < 8

Move right.

Continue Binary Search

The search gradually narrows until:

low = high = 13

Answer

The 8th smallest element is:

Why This Approach Is Efficient

A naive solution would:

Flatten the matrix.
Sort all elements.
Return the kth element.

This requires:

O(n² log n²)

time.

Using binary search on values avoids sorting altogether and takes advantage of the matrix's sorted structure.

Complexity Analysis

Time Complexity

Counting elements less than or equal to mid:

O(n)

Binary search on the value range:

O(log(max - min))

Overall:

O(n × log(max - min))

Space Complexity

O(1)

Only a few variables are used.

Pattern Recognition

This problem is a classic example of:

Binary Search on Answer
Search in a Sorted Matrix
Counting-Based Binary Search
Matrix Search Optimization
Order Statistics Problems

Similar techniques appear in:

Kth Smallest Pair Distance
Aggressive Cows
Capacity to Ship Packages
Allocate Minimum Pages
Median of a Sorted Matrix

Key Insight

The most important observation is that we are not searching for a position—we are searching for a value. By guessing a value and efficiently counting how many elements are less than or equal to it, we can eliminate half of the search space during every iteration. This transforms an expensive sorting problem into an efficient binary search problem.

Summary

The Kth Smallest Element in a Sorted Matrix problem demonstrates the power of Binary Search on Answer. Instead of flattening and sorting the matrix, we binary search over the range of values and count how many elements are less than or equal to a candidate value. Using a top-right traversal allows counting in O(n) time, resulting in an overall complexity of O(n × log(max - min)) with constant extra space.