Search a 2D Matrix
Search a 2D Matrix is a medium binary search problem solved with the 2d binary search + step search pattern.
The best approach, optimal (binary search on the flattened index), runs in O(log(m · n)) time and O(1) space.
Below are 2 approaches in Java, from staircase search up.
Problem
Each row of an m × n matrix is sorted, and the first value of each row is greater than the last value of the previous row. Decide whether target is in the matrix in O(log(m · n)) time.
Examples
Example 1
- Input
matrix = [[1,4,6],[9,12,15],[20,22,30]], target = 12- Output
true
Example 2
- Input
matrix = [[1,4,6],[9,12,15],[20,22,30]], target = 7- Output
false
Constraints
1 <= m, n <= 100- Rows are sorted and each row starts after the previous row ends.
- O(log(m · n)).
Animated walkthrough
A narrated, step-by-step animation that builds the solution from the idea up. Press play, or step through it at your own pace.
Concepts first, then the problem and every approach, step by step.
Space to play or pause · ← → to jump a step · click or drag the bar to seek
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the Java code.
| Approach | Time | Space |
|---|---|---|
| Staircase search | O(m + n) | O(1) |
| Optimal (binary search on the flattened index) | O(log(m · n)) | O(1) |
1Staircase search
O(m + n)O(1)Start at the top-right. Move left if the value is too big, down if it is too small.
- r = 0, c = n - 1; compare and move.
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int r = 0, c = matrix[0].length - 1;
while (r < matrix.length && c >= 0) {
if (matrix[r][c] == target) return true;
if (matrix[r][c] > target) c--; else r++;
}
return false;
}
}2Optimal (binary search on the flattened index)
O(log(m · n))O(1)Treat the matrix as a virtual sorted array of length m · n and binary search it, converting each mid to row mid / n and column mid % n.
- lo = 0, hi = m * n - 1.
- v = matrix[mid / n][mid % n]; compare with target.
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int lo = 0, hi = m * n - 1;
while (lo <= hi) {
int mid = (lo + hi) >>> 1;
int v = matrix[mid / n][mid % n];
if (v == target) return true;
if (v < target) lo = mid + 1; else hi = mid - 1;
}
return false;
}
}Edge cases to test
- Single row or single column
- Target smaller than matrix[0][0]
Hints
Hint 1
Read row by row, the matrix is one sorted array of length m · n. Index k maps to (k / n, k % n).
FAQ
What is the best time complexity for Search a 2D Matrix?
Optimal (binary search on the flattened index) runs in O(log(m · n)) time and O(1) extra space.
Which pattern does Search a 2D Matrix use?
It is a binary search problem that uses the 2d binary search + step search pattern. Other problems with the same pattern: Row with max 1s, Search a 2D Matrix II (Young Tableau).
Is there a brute force solution for Search a 2D Matrix?
Yes. Staircase search takes O(m + n) time and O(1) space. Start at the top-right.
Which edge cases should I test for Search a 2D Matrix?
Single row or single column; Target smaller than matrix[0][0].