# Ac solution code

• The key point of Divide&Conquer is discarding efficiently, which is actually the key point of all algorithms.

In this question, top-right point is the kind of the middle point of the matrix. (if we imagine a line crossing top-left=>top-right=>bottom-right of the matrix. This line is exactly in the ascending order.)

``````Say top-right point is matrix[i][j] (i = 0..rows-1; j = 0..columns-1)
1) if matrix[i][j] == target, return true;
2) if matrix[i][j] > target, we discard jth column (Because matrix[i][j] is top-right, which means all numbers in jth column >= matrix[i][j]);
3) if matrix[i][j] < target, we discard ith row (Because matrix[i][j] is top-right, which means all numbers in ith row <= matrix[i][j]).
``````

Time complexity = O(m + n)

As there's only one pass, and i is 0..n-1, j is 0..m-1, so the complexity is O(m + n).

JAVA Code:

``````public boolean searchMatrix(int[][] matrix, int target) {
int rows = matrix.length, cols = matrix[0].length, i = 0, j = cols - 1;
while (i < rows && j >=0) {
if (matrix[i][j] == target) return true;
else if (matrix[i][j] > target) j--;
else i++;
}
return false;
}``````

• very clear explaination. Thanks.

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