Number of Corner Rectangles


  • 0

    Click here to see the full article post


  • 2

    I think the space complexity for Approach #1 is C^2 because the total number of combinations within the Counter is only C^2.


  • 0
    H

    I have an O(R * C ^ 2) time solution that managed to pass all tests... First I need an O(C ^ 2) time run to index all corner pairs in the row, and then repeat it R times for all rows. Knowing the number of matching corner pairs, the rest of the math is easy with a pair counter class.


  • 0
    L

    Nice observation!
    I just reply a rewrite version of Approach #1 for those who also get a little bit confused by the way the original code iterates through the rows and columns. Please ignore mine if you feel that one is easier to understand.

        def countCornerRectangles(self, grid):
            ans =0
            counter = collections.Counter()
            for rowi in range(len(grid)):
                for col1 in range(len(grid[rowi])):
                    if grid[rowi][col1]:
                        for col2 in xrange(col1+1, len(grid[rowi])):
                            if grid[rowi][col2]:
                                ans += counter[col1,col2]
                                counter[col1,col2] += 1
            return ans
    

  • 0
    P

    The Time Complexity of Approach #2 is wrong. It should be at least O(R*C)
    Because of the follow code:

    for (int r = 0; r < grid.length; ++r) {
                rows.add(new ArrayList());
                for (int c = 0; c < grid[r].length; ++c)
                    if (grid[r][c] == 1) {
                        rows.get(r).add(c);
                        N++;
                    }
            }
    

  • 0
    B

    @protocols1919
    Yes, it is O(Nsqrt(N) + RC).


  • 0
    M

    For solution 2, there can be at most R "weak rows" and each row take O(N). So I think the time complexity would be O(N(R+sqrtN) + RC). Please correct me if I am wrong..


  • 0
    A

    For solution 2, when a heavy row arrives, it uses O(N) time to count as it goes over all the 1's in all rows(i.e, count the rectangles between this heavy row with all the other rows). Consider a light row arrives, it uses O(N) time to enumerate all pairs of 1's in its row. Let the number of heavy row be h, then the time for heavy row with all the other rows is O(hN); for light row, it is O(N(R - h)), where R is the number of rows. Therefore the total counting time is O(NR). Plus the preprocessing step, it should be O(RN + RC), where C is the number of columns.

    All right, here comes the more sophisticated analysis for the light row part. Indeed, suppose we have k light rows, each have s_1, s_2, ..., s_k 1's in their rows. Then the exact computation time for the light row part counting is the sum of (s_i)^2 over all these rows. Assume s_1 >= s_2 >= ... >= s_k, if s_1 is smaller than \sqrt(N), one can reduce s_k by 1 and add it to s_1 to get a larger sum of (s_i)^2. Therefore one could conclude that the largest value of this sum of squares happens when s_1 = s_2 = ... s_{p-1} = \sqrt(N) and s_p < \sqrt(N) for some p is roughly \sqrt(N). This gives the upper bound for the light row part which is O(N\sqrt(N)). As there are at most \sqrt(N) heavy rows and each row spends O(N) time. Therefore the time complexity is O(N\sqrt(N) + RC).


  • 0
    H

    It seems to me that the second approach degrades in case of a matrix with a lot of 1s. Is that the case?


Log in to reply
 

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