Share my O(m+n) solution

  • 5

    I search from right up corner:row=0,col=m-1

    1. if matrix[row][col] is equal target,return true.
    2. if matrix[row][col] is less than target, row++; indicate that this row can't contain target.because this one in this line is the biggest one,counting from 'row'.
    3. if matrix[row][col] is greater than target,col--; indicate that this column can't contain target.because this one in this column is the smallest one,counting from 'col'.

    class Solution {
        bool searchMatrix(vector<vector<int> > &matrix, int target) {
            if(matrix.empty())return false;
            int n=matrix.size(),m=matrix[0].size(),row=0,col=m-1;
                if(matrix[row][col]==target)return true;
                else if(matrix[row][col]<target)row++;
                else col--;
            return false;

  • 2

    It's O(m + n), not O(max(m, n)). The worst situation will be at the last row and the first column.

    There is a solution has O(logm + logn)

  • 0

    thanks,u are right

Log in to reply

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