Artful C++ code with O(max(m,n)), AC with beating 98% c++

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

};``````

• The worst case for your solution is like this:

matrix = [[1,2,3,4,5,6....100000000]]
target = 0

Your solution will traversal the whole matrix. Much slower than the binary search.

• "Also your time complexity is O(m+n), not O(max(m, n))"

O(m+n) and O(max(m, n)) are the same.

• This post is deleted!

• If that was your point, then you completely screwed up expressing it :-P
You said it's not O(max(m,n)), which is just false.

Your argument now also doesn't convince me. I could just as well say "we should write max(m,n). Usually someone write m+n (in general not in big O), the idea that the smaller part can't be avoid." (To be clear: That's not what I think. I disagree with it just like I disagree with your original statement. I think both O(m+n) and O(max(m,n)) are perfectly fine.)

• OK. Let me remove the wrong statement then~

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