# Share my O(n + m) solution

• ``````  Solution {  public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int n = (int)matrix.size();
int m = (int)matrix[0].size();
--n; --m;
while(n > 0 && matrix[n - 1][m] >= target) --n;
while(m > 0 && matrix[n][m - 1] >= target) --m;
return (matrix[n][m] == target);
}
};
``````

I just used that fact, that number in the matrix increases

• Good job, bro!

• I think your solution is not optimal!
The solution below has O(lonN + logM) time complexity.
idea is very similar to your but I used bin_search.

``````class Solution {
public:
bool searchMatrix(vector<vector<int> > &matrix, int target) {
int n = matrix.size() - 1, m = matrix[0].size() - 1;
int l = 1, r = n;
// Let's find a row where may be our target
while (l <= r){
int mid = l + (r - l) / 2;
if (matrix[mid - 1][m] == target) return true;
if (matrix[mid - 1][m] > target) r = mid - 1; else l = mid + 1;
}
int row = r;
l = 0, r = m;
while (l <= r){
int mid = l + (r - l) / 2;
if (matrix[row][mid] == target) return true;
if (matrix[row][mid] > target) r = mid - 1; else l = mid + 1;
}
return false;
}
};``````

• why you start at the second row( int l = 1, r = n;) when find the row may contain the target?
I can not figure out why my solution get RE, just a little different from yours. In my solution, I assign the `low = 0`.

• It allows me not to go out from array. You should notice that I consider matrix[mid - 1][m].

• Although not optimal solution ,still is a very well though one

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