One of the easiest ways to miss this problem is to focus on the matrix structure instead of the ordering property.
Problem
Given an m x n matrix where:
- Each row is sorted in ascending order.
- The first element of each row is greater than the last element of the previous row.
Determine if a target value exists in the matrix.
Brute Force Approach
Traverse every cell and compare it with the target.
for(int i = 0; i < matrix.length; i++) {
for(int j = 0; j < matrix[0].length; j++) {
if(matrix[i][j] == target) {
return true;
}
}
}
return false;
Complexity
- Time: O(M × N)
- Space: O(1)
Key Observation
Consider the matrix:
1 3 5 7
10 11 16 20
23 30 34 60
It can be viewed as a sorted 1D array:
1 3 5 7 10 11 16 20 23 30 34 60
Since the entire matrix is globally sorted, we can apply Binary Search directly.
The Trick
For a virtual index mid:
row = mid / cols;
col = mid % cols;
This converts a 1D index back into a 2D position.
Example:
mid = 6;
row = 6 / 4 = 1;
col = 6 % 4 = 2;
So we access:
matrix[1][2]
Optimal Solution
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length;
int cols = matrix[0].length;
int low = 0;
int high = rows * cols - 1;
while (low <= high) {
int mid = low + (high - low) / 2;
int row = mid / cols;
int col = mid % cols;
if (matrix[row][col] == target) {
return true;
} else if (matrix[row][col] > target) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
}
}
Complexity
- Time: O(log(M × N))
- Space: O(1)
Common Mistake
Many candidates write:
while(low < high)
This skips the final element when:
low == high
Since Binary Search uses an inclusive search range [low, high], always use:
while(low <= high)
Interview Takeaway
Whenever a matrix satisfies:
First element of a row > Last element of previous row
Think:
"This matrix behaves like a sorted 1D array."
Then use Binary Search with:
row = mid / cols;
col = mid % cols;
and the problem becomes a standard Binary Search question.
Thanks for reading! 🚀
Top comments (0)