Introduction
This problem asks us to find the kth smallest element in an n × n matrix where:
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:
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:
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:
2
Since:
2 < 8
Move right.
Continue Binary Search
The search gradually narrows until:
low = high = 13
Answer
13
The 8th smallest element is:
13
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.