Number of Corner Rectangles


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


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_{p1} = \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).