# Share my O(m+n) solution

• I search from right up corner:row=0,col=m-1

1. if matrix[row][col] is equal target,return true.
2. if matrix[row][col] is less than target, row++; indicate that this row can't contain target.because this one in this line is the biggest one,counting from 'row'.
3. if matrix[row][col] is greater than target,col--; indicate that this column can't contain target.because this one in this column is the smallest one,counting from 'col'.

``````class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
if(matrix.empty())return false;
int n=matrix.size(),m=matrix[0].size(),row=0,col=m-1;
while(row<n&&col>=0){
if(matrix[row][col]==target)return true;
else if(matrix[row][col]<target)row++;
else col--;
}
return false;
}
};``````

• It's O(m + n), not O(max(m, n)). The worst situation will be at the last row and the first column.

There is a solution has O(logm + logn)

• thanks，u are right

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