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


  • 3
    S
    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;
        }
        
    };

  • 0

    What's "artful" about this? Am I missing something?


  • 0

    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.


  • 0

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

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


  • 0
    This post is deleted!

  • 0

    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.)


  • 0

    OK. Let me remove the wrong statement then~


Log in to reply
 

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