Binary search in diagonal element! O(log^2 n*m)maybe? Share my thinking process..


  • 2

    Well, as the problem states,think of an 2x2 matrix,
    [
    a, b;
    c, d;
    ]
    we can clearly know that a is the min number and d is the max number,
    the we put this 2x2 matrix into a big matrix:

    ............... ....................
    .....Z1........ .........Z2.........
    ...............  ...................
    ..............a b...................
    ..............c d...................
    ......Z3....... .........Z4.........
    ................ ...................
    
    • If the target is >a and <d, we can discard elements in Z1 and Z4!
      (since all elements in Z4 is bigger than d && all elements in Z1 is
      smaller than Z1).
    • Then we redo the process in Z2 and Z3.

    So,how to find a and d?Because the diagonal elements is ordered, we just simply binary search in the diagonal elements and find the lower bound of our target.

    Suppose N=n*m;
    we get T(N)=2T(N/2)+O(lgN)
    T(N)=O(lg^2N)?


  • 1

    That's one of the rarer approaches, but no, it's neither new nor O(lg^2N). Your T(N)=T(N/2)+O(lgN) is wrong in two ways:

    • You have *two* subproblems and can't just pretend they're only one.
    • If the abcd-block is in a corner of the matrix, then the larger subproblem can be far larger than N/2. Almost N.

  • 0

    yeah, I found it later... the size of my subproblem is not sure.... But I wonder how to calculate the time complexity of this approache? Thanks for your comment any way~


  • 0

    Your new version, the T(N)=2T(N/2)+O(lgN), results in Θ(N), not O(lg^2N).

    Not sure why you say N/2, though. It's still invalid, and if you mean the two subproblems being equally large, it should be N/4. And T(N)=2T(N/4)+O(lgN) leads to Θ(sqrt(N)).

    Not sure how to analyze it properly and I don't really want to, but maybe 1337c0d3r's article can help.


  • 0

    Thank you! the article really helps me.


Log in to reply
 

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