Given a grid where each entry is only 0 or 1, find the number of corner rectangles.
A corner rectangle is 4 distinct 1s on the grid that form an axis-aligned rectangle. Note that only the corners need to have the value 1. Also, all four 1s used must be distinct.
Example 1:
Input: grid = [[1, 0, 0, 1, 0], [0, 0, 1, 0, 1], [0, 0, 0, 1, 0], [1, 0, 1, 0, 1]] Output: 1 Explanation: There is only one corner rectangle, with corners grid[1][2], grid[1][4], grid[3][2], grid[3][4].
Example 2:
Input: grid = [[1, 1, 1], [1, 1, 1], [1, 1, 1]] Output: 9 Explanation: There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.
Example 3:
Input: grid = [[1, 1, 1, 1]] Output: 0 Explanation: Rectangles must have four distinct corners.
Note:
grid will each be in the range [1, 200].grid[i][j] will be either 0 or 1.1s in the grid will be at most 6000.Intuition
\nWe ask the question: for each additional row, how many more rectangles are added?
\nFor each pair of 1s in the new row (say at new_row[i] and new_row[j]), we could create more rectangles where that pair forms the base. The number of new rectangles is the number of times some previous row had row[i] = row[j] = 1.
Algorithm
\nLet\'s maintain a count count[i, j], the number of times we saw row[i] = row[j] = 1. When we process a new row, for every pair new_row[i] = new_row[j] = 1, we add count[i, j] to the answer, then we increment count[i, j].
Complexity Analysis
\nTime Complexity: where is the number of rows and columns.
\nSpace Complexity: in additional space.
\nIntuition and Algorithm
\nCan we improve on the ideas in Approach #1? When a row is filled with 1s, we do work to enumerate every pair of 1s. This is okay when is small, but expensive when is big.
\nSay the entire top row is filled with 1s. When looking at the next row with say, f 1s that match the top row, the number of rectangles created is just the number of pairs of 1s, which is f * (f-1) / 2. We could find each f quickly using a Set and a simple linear scan of each row.
Let\'s call a row to be heavy if it has more than points. The above algorithm changes the complexity of counting a heavy row from to , and there are at most heavy rows.
\n\nComplexity Analysis
\nTime Complexity: where is the number of ones in the grid.
\nSpace Complexity: in additional space, for rows, target, and count.
Analysis written by: @awice.
\n