This website contains ALL LeetCode **Premium** problems for
**FREE!!**.

All leaked interview problems are collected from Internet.

All leaked interview problems are collected from Internet.

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:1Explanation: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:9Explanation:There are four 2x2 rectangles, four 2x3 and 3x2 rectangles, and one 3x3 rectangle.

**Example 3:**

Input:grid = [[1, 1, 1, 1]]Output:0Explanation:Rectangles must have four distinct corners.

**Note:**

- The number of rows and columns of
`grid`

will each be in the range`[1, 200]`

. - Each
`grid[i][j]`

will be either`0`

or`1`

. - The number of
`1`

s in the grid will be at most`6000`

.

b'

\n\n#### Approach #1: Count Corners [Accepted]

\n

\n#### Approach #2: Heavy and Light Rows [Accepted]

\n

\n

'
**Intuition**

We 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**

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**

- \n
- \n
Time Complexity: where is the number of rows and columns.

\n \n - \n
Space Complexity: in additional space.

\n \n

\n

**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**

- \n
- \n
Time Complexity: where is the number of ones in the grid.

\n \n - \n
Space Complexity: in additional space, for

\n`rows`

,`target`

, and`count`

. \n

\n

Analysis written by: @awice.

\n