C++ Solution, 139ms, with explanation


  • 0
    J

    The idea here is to narrow down the matrix to get a sub-matrix indicated by [rbegin:rend][cbegin:cend].
    For the beginning row, if its largest value (i.e., at end of the row) is less than the target, make the rbegin++, if its largest value is larger than the target, make the cend--.
    For the last row, if the smallest value larger (i.e., at the beginning of the row) than the target, make the rend--, if its value smaller than the target, make the cbegin++.

    After every iteration, the sub-matrix will become smaller and smaller.

        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            
            int rbegin=0, cbegin=0, rend=matrix.size()-1, cend=matrix[0].size()-1;
            if(rend<0 || cend<0 || target<matrix[0][0] || target>matrix[rend][cend]) return false;
            while(rbegin<=rend && cbegin<=cend){
                int tmp=matrix[rbegin][cend];
                if(tmp<target) rbegin++;
                else if(tmp>target) cend--;
                else return true;
                
                tmp=matrix[rend][cbegin];
                if(tmp>target) rend--;
                else if(tmp<target) cbegin++;
                else return true;
    
                if(rbegin>rend || cbegin>cend) return false;
            }
            return matrix[rbegin][cbegin]==target;
        }
    

Log in to reply
 

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