# LeetCode 750: Number Of Corner Rectangles

## Problem Restatement

We are given an `m x n` binary matrix `grid`.

Each cell is either `0` or `1`.

We need to count how many axis-aligned rectangles can be formed where all four corner cells are `1`.

Only the corners need to be `1`. The cells inside the rectangle and along its edges may be either `0` or `1`.

All four corner cells must be distinct. So a single row or a single column cannot form a rectangle.

## Input and Output

| Item | Meaning |
|---|---|
| Input | Binary matrix `grid` |
| Output | Number of valid corner rectangles |
| Valid rectangle | Four distinct corner cells are `1` |
| Rectangle type | Axis-aligned |
| Interior cells | Do not matter |

Example function shape:

```python
def countCornerRectangles(grid: list[list[int]]) -> int:
    ...
```

## Examples

### Example 1

```python
grid = [
    [1, 0, 0, 1, 0],
    [0, 0, 1, 0, 1],
    [0, 0, 0, 1, 0],
    [1, 0, 1, 0, 1],
]
```

There is one valid rectangle.

Its corners are:

```text
grid[1][2]
grid[1][4]
grid[3][2]
grid[3][4]
```

The answer is:

```python
1
```

### Example 2

```python
grid = [
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
]
```

Choose any two rows and any two columns.

There are:

```text
C(3, 2) * C(3, 2) = 3 * 3 = 9
```

valid rectangles.

The answer is:

```python
9
```

### Example 3

```python
grid = [[1, 1, 1, 1]]
```

There is only one row.

A rectangle needs two distinct rows.

The answer is:

```python
0
```

## First Thought: Choose Two Rows and Two Columns

A direct way is:

1. Pick two different rows.
2. Pick two different columns.
3. Check whether all four corners are `1`.

This is correct, but it costs:

```text
O(m^2 * n^2)
```

With up to `200` rows and `200` columns, this can be larger than necessary.

We need to reuse information about previous rows.

## Key Insight

A rectangle is determined by:

1. A pair of columns.
2. Two rows that both have `1` in those columns.

For example, suppose a row has `1` at columns:

```python
2
4
```

If some earlier row also had `1` at columns `2` and `4`, then those two rows form a rectangle using column pair `(2, 4)`.

So we process rows one by one.

For each row, generate every pair of columns where both cells are `1`.

Use a hash map:

```python
pair_count[(c1, c2)]
```

This stores how many previous rows had `1` in both columns `c1` and `c2`.

When the current row also has that pair, every previous row counted there forms one new rectangle.

## Algorithm

Create an empty counter:

```python
pair_count = {}
```

Initialize:

```python
answer = 0
```

For each row:

1. Find every pair of columns `(c1, c2)` where both values are `1`.
2. Add `pair_count[(c1, c2)]` to `answer`.
3. Increment `pair_count[(c1, c2)]`.

The order matters.

We count rectangles using previous rows first, then record the current row for future rows.

## Correctness

Every valid corner rectangle has two distinct rows and two distinct columns. Let the lower row be processed later than the upper row.

When the algorithm reaches the lower row, it considers the exact pair of columns that form the rectangle. Since the upper row already had `1` in both of those columns, it was counted in `pair_count[(c1, c2)]`.

Therefore this rectangle is added exactly once when the lower row is processed.

The algorithm never counts an invalid rectangle. It only adds to the answer when the current row has two `1`s at columns `c1` and `c2`, and a previous row also had two `1`s at those same columns. These four cells form an axis-aligned rectangle with four distinct corners.

Since every valid rectangle is counted once and only once, the algorithm returns the correct count.

## Complexity

Let `m` be the number of rows and `n` be the number of columns.

| Metric | Value | Why |
|---|---:|---|
| Time | `O(m * n^2)` | For each row, we examine pairs of columns |
| Space | `O(n^2)` | The counter may store every column pair |

The official constraints allow `m, n <= 200`, and the number of `1`s is at most `6000`.

## Implementation

```python
from collections import defaultdict

class Solution:
    def countCornerRectangles(self, grid: list[list[int]]) -> int:
        rows = len(grid)
        cols = len(grid[0])

        pair_count = defaultdict(int)
        answer = 0

        for r in range(rows):
            for c1 in range(cols):
                if grid[r][c1] == 0:
                    continue

                for c2 in range(c1 + 1, cols):
                    if grid[r][c2] == 0:
                        continue

                    answer += pair_count[(c1, c2)]
                    pair_count[(c1, c2)] += 1

        return answer
```

## Code Explanation

The dictionary stores how many previous rows contain each column pair:

```python
pair_count = defaultdict(int)
```

For each row, we try all pairs of columns:

```python
for c1 in range(cols):
    ...
    for c2 in range(c1 + 1, cols):
```

We only care about pairs where both cells are `1`:

```python
if grid[r][c1] == 0:
    continue

if grid[r][c2] == 0:
    continue
```

If the current row has `1`s at `(c1, c2)`, then every previous row with the same pair creates one rectangle:

```python
answer += pair_count[(c1, c2)]
```

Then the current row becomes available for future rows:

```python
pair_count[(c1, c2)] += 1
```

## Testing

```python
def run_tests():
    s = Solution()

    assert s.countCornerRectangles([
        [1, 0, 0, 1, 0],
        [0, 0, 1, 0, 1],
        [0, 0, 0, 1, 0],
        [1, 0, 1, 0, 1],
    ]) == 1

    assert s.countCornerRectangles([
        [1, 1, 1],
        [1, 1, 1],
        [1, 1, 1],
    ]) == 9

    assert s.countCornerRectangles([[1, 1, 1, 1]]) == 0

    assert s.countCornerRectangles([
        [1],
        [1],
        [1],
    ]) == 0

    assert s.countCornerRectangles([
        [1, 1],
        [1, 1],
    ]) == 1

    assert s.countCornerRectangles([
        [1, 0, 1],
        [1, 0, 1],
        [1, 1, 1],
    ]) == 3

    print("all tests passed")

run_tests()
```

| Test | Why |
|---|---|
| Standard example | One valid rectangle |
| Full `3 x 3` grid | Counts all row-pair and column-pair combinations |
| One row | Cannot form a rectangle |
| One column | Cannot form a rectangle |
| Full `2 x 2` grid | Minimum valid rectangle |
| Mixed grid | Multiple rectangles sharing rows or columns |