C++ solution, quicker than MlogN solutions but not sure about time complexity.


  • 1
    P

    My Code:

    class Solution {
    public:
        bool searchMatrix(vector<vector<int>>& matrix, int target) {
            int r=matrix.size();
            if(r==0) return false;
            int c=matrix[0].size();
            if(c==0) return false;
            return subsrh(matrix,target,0,0,r-1,c-1);
        }
    private:
        bool subsrh(vector<vector<int>>& matrix, int target, int x1, int y1, int x2, int y2){
            if(x1>x2||y1>y2||target<matrix[x1][y1]||target>matrix[x2][y2]) return false;
            if(x2-x1<=1&&y2-y1<=1)
                return target==matrix[x2][y2]||target==matrix[x1][y1]||target==matrix[x2][y1]||target==matrix[x1][y2];
            int m1=(x1+x2)/2, m2=(y1+y2)/2;
            if(matrix[m1][m2]==target) return true;
            else if(matrix[m1][m2]>target) 
                return subsrh(matrix, target, x1, y1, m1-1, y2)||subsrh(matrix, target, m1, y1, x2,m2-1);
            else {
                return subsrh(matrix, target, x1, m2+1, x2, y2)||subsrh(matrix, target, m1+1, y1, x2, m2);
            }
        }
    };
    

    Time complexity? I can't solve this T(MN)=T(MN/2)+T(MN/4)+O(1).

    Updates: Thanks to @StefanPochmann

    T(MN) ≈ Θ((MN)^0.694),


  • 0

    "Time complexity? I can't solve this T(MN)=T(MN/2)+T(MN/4)+O(1)."

    Using the Akra–Bazzi method, I get p≈0.694 and end up with T(MN) ≈ Θ((MN)^0.694), which I think is worse than MlogN.

    Not entirely sure I did that correctly, though. Don't know what "sufficient base cases are provided" means, and whether I can really treat MN like one variable, for example because a 1x1000000 matrix is much easier than a 1000x1000 matrix, even though they contain the same number of elements...


  • 0
    P

    Thank you for leading me to the Akra–Bazzi method. I found a better source here: http://courses.csail.mit.edu/6.046/spring04/handouts/akrabazzi.pdf

    I get the same p≈0.694 in this case we treat MN like one variable. But by comparing it to MlogN the answer depends on how M scales with N. if M~O(N^q) when q>=2.333, Θ((MN)^0.694) is faster, when q<2.333, MlogN is faster.

    BTW, do you know if there is an optimal solution to this problem in the sense of time complexity?


Log in to reply
 

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