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

Example function shape:

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

Examples

Example 1

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:

grid[1][2]
grid[1][4]
grid[3][2]
grid[3][4]

The answer is:

1

Example 2

grid = [
    [1, 1, 1],
    [1, 1, 1],
    [1, 1, 1],
]

Choose any two rows and any two columns.

There are:

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

valid rectangles.

The answer is:

9

Example 3

grid = [[1, 1, 1, 1]]

There is only one row.

A rectangle needs two distinct rows.

The answer is:

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:

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:

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:

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:

pair_count = {}

Initialize:

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 1s at columns c1 and c2, and a previous row also had two 1s 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.

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

Implementation

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:

pair_count = defaultdict(int)

For each row, we try all pairs of columns:

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

We only care about pairs where both cells are 1:

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

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

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

answer += pair_count[(c1, c2)]

Then the current row becomes available for future rows:

pair_count[(c1, c2)] += 1

Testing

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()