Problem Description
Write an efficient algorithm that searches for a value target in an m x n integer matrix matrix. This matrix has the following properties:
- Integers in each row are sorted in ascending from left to right.
- Integers in each column are sorted in ascending from top to bottom.
Solution
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
class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length;
int columns = matrix[0].length;
//Start the search from top right corner
int i=0, j=columns-1;
while(i<rows && j>=0){
int current = matrix[i][j];
if(target == current) return true;
//If target is more than current element, go down
if(target > current) i++;
//Else go left
else j--;
}
return false;
}
}