750. Number Of Corner Rectangles


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:

  1. The number of rows and columns of grid will each be in the range [1, 200].
  2. Each grid[i][j] will be either 0 or 1.
  3. The number of 1s in the grid will be at most 6000.


Approach #1: Count Corners [Accepted]

Intuition

We ask the question: for each additional row, how many more rectangles are added?

For 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

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 count[i, j].

Complexity Analysis

  • Time Complexity: where is the number of rows and columns.

  • Space Complexity: in additional space.

Approach #2: Heavy and Light Rows [Accepted]

Intuition and Algorithm

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.

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.

Complexity Analysis

  • Time Complexity: where is the number of ones in the grid.

  • Space Complexity: in additional space, for rows, target, and count.

Analysis written by: @awice.

Submit Solution