Search a 2D Matrix 2 - Rows and columns are sorted
Medium
Subtopics
array·binary-search·divide-and-conquer·matrix
Companies
adobe·amazon·apple·baidu·bloomberg·bytedance·citadel·ebay·expedia·facebook·goldman-sachs·google·linkedin·microsoft·oracle·paypal·salesforce·sap·tencent·yahooLast updated: Aug 1, 2025
We can use a divide-and-conquer approach by recursively partitioning the matrix into four quadrants. At each step, we check the center element. If it matches the target, we return true. If the target is less than the center, it cannot be in the bottom-right quadrant (all values there are larger), so we search the other three quadrants. If the target is greater, it cannot be in the top-left quadrant, so we search the other three. This way, we eliminate about a quarter of the matrix at each step.
To visualize, if the center of the matrix is y, the matrix is divided as:
1
2
3
A | B
--+--
C | D
Where:
A is the upper-left quadrant
B is the upper-right quadrant
C is the bottom-left quadrant
D is the bottom-right quadrant
If the target x is less than y, it cannot be in D (all values there are greater than y), so we search A, B, and C.
If the target x is greater than y, it cannot be in A (all values there are less than y), so we search B, C, and D.
Since each row is sorted, we can perform a binary search on each row to check if the target exists. This leverages the row-wise sorting for efficient searching, but does not use the column-wise sorting.
classSolution {
publicbooleansearchMatrix(int[][] matrix, int target) {
for (int[] row : matrix) {
int l = 0, r = row.length- 1;
while (l <= r) {
int m = l + (r - l) / 2;
if (row[m]== target) returntrue;
if (row[m]< target) l = m + 1;
else r = m - 1;
}
}
returnfalse;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
classSolution {
funsearchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
for (row in matrix) {
var l = 0var r = row.size - 1while (l <= r) {
val m = l + (r - l) / 2when {
row[m] == target ->returntrue row[m] < target -> l = m + 1else-> r = m - 1 }
}
}
returnfalse }
}
1
2
3
4
5
6
7
8
classSolution:
defsearchMatrix(self, matrix: list[list[int]], target: int) -> bool:
from bisect import bisect_left
for row in matrix:
i = bisect_left(row, target)
if i < len(row) and row[i] == target:
returnTruereturnFalse
This method leverages the sorted property of both rows and columns. By starting from the top-right (or bottom-left) corner, we can eliminate either a row or a column at each step:
If the current element is less than the target, move down (since all elements below are larger in the same column).
If the current element is greater than the target, move left (since all elements to the left are smaller in the same row).
If the current element matches the target, return true.
This approach efficiently narrows down the search space in a single pass.
classSolution {
public:bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(), n = matrix[0].size();
int row =0, col = n -1;
while (row < m && col >=0) {
if (matrix[row][col] == target) return true;
elseif (matrix[row][col] < target) row++;
else col--;
}
return false;
}
};
classSolution {
publicbooleansearchMatrix(int[][] matrix, int target) {
int m = matrix.length, n = matrix[0].length;
int row = 0, col = n - 1;
while (row < m && col >= 0) {
if (matrix[row][col]== target) returntrue;
elseif (matrix[row][col]< target) row++;
else col--;
}
returnfalse;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
classSolution {
funsearchMatrix(matrix: Array<IntArray>, target: Int): Boolean {
val m = matrix.size
val n = matrix[0].size
var row = 0var col = n - 1while (row < m && col >=0) {
when {
matrix[row][col] == target ->returntrue matrix[row][col] < target -> row++else-> col-- }
}
returnfalse }
}
1
2
3
4
5
6
7
8
9
10
11
12
classSolution:
defsearchMatrix(self, matrix: list[list[int]], target: int) -> bool:
m, n = len(matrix), len(matrix[0])
row, col =0, n -1while row < m and col >=0:
if matrix[row][col] == target:
returnTrueelif matrix[row][col] < target:
row +=1else:
col -=1returnFalse
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
impl Solution {
pubfnsearch_matrix(matrix: Vec<Vec<i32>>, target: i32) -> bool {
let (m, n) = (matrix.len(), matrix[0].len());
let (mut row, mut col) = (0, n asi32-1);
while row < m && col >=0 {
let val = matrix[row][col asusize];
if val == target {
returntrue;
} elseif val < target {
row +=1;
} else {
col -=1;
}
}
false }
}
⏰ Time complexity: O(m + n), where m is the number of rows and n is the number of columns. In the worst case, we traverse at most m rows and n columns.
🧺 Space complexity: O(1), as we use only a constant amount of extra space.