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.
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, grid, grid, grid.
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.
Input: grid = [[1, 1, 1, 1]] Output: 0 Explanation: Rectangles must have four distinct corners.
gridwill each be in the range
grid[i][j]will be either
1s in the grid will be at most
We ask the question: for each additional row, how many more rectangles are added?\n
For each pair of 1s in the new row (say at
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.
Let\'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
Time Complexity: where is the number of rows and columns.\n
Space Complexity: in additional space.\n
Intuition and Algorithm\n
Can 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.\n
Say 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\n
Time Complexity: where is the number of ones in the grid.\n
Space Complexity: in additional space, for
Analysis written by: @awice.\n