c++ O(m+n) solution

  • 1

    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 {
        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;
                    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.