c++ O(m+n) solution


  • 1
    B

    the idea here is:
    start from top right corner (or bottom left corner as you wish), thus all pixels above the diagonal are smaller than it.
    If target is smaller, we move 1 step to the left cuz the target only could be on diagonal or above the diagonal.
    Keep searching like this till end...

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

Log in to reply
 

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