O(logm+logn) solution is impossible for this problem


  • 1
    M

    m:=#rows, n:=#cols


    O(m+n) time sol: use the upper-right corner and compare to target, if corner==target return true, else if corner > target 'delete' last col, if corner < target, 'delete' first row. Continue after you hit the lower-left corner.

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

    O(mlgn) time sol. Loop over each row of the matrix, do binary search on each row. (no code)


    O(nlgm) time sol. Loop over each col of the matrix, do binary search on each col. (since the data structure is 2D array, it is doable) (no code)


    O(logm + logn) time sol is impossible. I made a mistake in claiming the following solution is O(logm + logn). But actually the time should be T(m,n) = T(m/2,n) + T(m/2,n/2) + c, which is not O(logm + logn)

    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.empty()) return false;
        return search(matrix,target,0,matrix.size()-1,0,matrix[0].size()-1);
    }
    
    bool search(const vector<vector<int>>& matrix, int target, int m0, int m1, int n0, int n1) const {
        if(m0>m1 || n0>n1) return false;
        int i=m0+(m1-m0)/2, j=n0+(n1-n0)/2;
        if(matrix[i][j]==target) 
            return true;
        else if(matrix[i][j]<target)
            return search(matrix,target,m0,m1,j+1,n1) || search(matrix,target,i+1,m1,n0,j);
        else 
            return search(matrix,target,m0,i-1,n0,n1) || search(matrix,target,i,m1,n0,j-1);
    }

  • 0

    As discussed before, O(logm + logn) is impossible. Your analysis is wrong.


  • 0
    M

    Yes. The O(logm + logn) analysis is clearly wrong. Thanks for pointing this out, StefanPochmann.

    One cannot pick the 'center' cell of a matrix, compare it to the target value, and claim to eliminate some blocks of the matrix. One has to do binary search in a row to eliminate half of the matrix (for quick reference see the stacksoverflow post in StefanPochmann's post above)


  • 0
    X

    the last one is T(nxn) = O(n^log3)


  • 0
    This post is deleted!

  • 0

    One cannot pick the 'center' cell of a matrix, compare it to the target value, and claim to eliminate some blocks of the matrix.

    Wait, what? You can do that and your code does. The mistake is just that you ignored the overhead of organizing the sub-blocks.


  • 0
    M

    Thank you. Is it correct to say that the last solution's time complexity is: T(N,M) = c + T(N/2, M) + T(N/2, M/2) <==> T(N,M) is not O(logM + logN)


Log in to reply
 

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