My Java solution with O(n) time

• public class Solution {

``````public boolean searchMatrix(int[][] matrix, int target) {
int row = 0;
/*empty，return false*/
if(matrix.length == 0)
return false;
/*out of bounds，return false*/
if(target > matrix[matrix.length - 1][matrix[matrix.length - 1].length - 1] || target < matrix[0][0])
return false;
/*compare the target with the first ele of each row*/
for(int i = 0; i < matrix.length; i++) {
if(target == matrix[i][0])
return true;
if(target < matrix[i][0]) {
row = i - 1;
break;
}
if(i == matrix.length - 1 && target > matrix[i][0]) {
row = matrix.length - 1;
break;
}
}
/*search the row*/
for(int j = 0; j < matrix[row].length; j++) {
if(matrix[row][j] == target)
return true;
}
return false;
}
``````

}

• this will degrade to iterate all numbers, considering 1*N matrix

• This is not true I think, you just check one row, but in fact it could contains in many possible rows where the head is less than target while the last one is larger than the target

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.