LeetCode - Search a 2D Matrix
Problem description
Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:
Integers in each row are sorted from left to right. The first integer of each row is greater than the last integer of the previous row. Example 1:
1
2
3
4
5
6
7
8
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 3
Output: true
Example 2:
1
2
3
4
5
6
7
8
Input:
matrix = [
[1, 3, 5, 7],
[10, 11, 16, 20],
[23, 30, 34, 50]
]
target = 13
Output: false
Analysis
Because of we have each row sorted and each column sorted, so we have to use these rules to make it search more efficiently. If we consider one cell with value v in matrix, if target > v, then the target should locate in right and down part of the matrix. And if target < v, then the target should locate in left and up part in matrix. So we can move left if v > target and down if v < target. This method always used when search in 2D matrix with sorted.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null){
return false;
}
int m = matrix.length;
if (m == 0){
return false;
}
int n = matrix[0].length;
if (n == 0){
return false;
}
int i = 0, j = n-1;
while (i < m && j >= 0){
if (matrix[i][j] == target){
return true;
}
else if (matrix[i][j] > target){
j--;
}
else{
i++;
}
}
return false;
}
}