LeetCode 750 - Number Of Corner Rectangles

The problem asks us to count the number of corner rectangles in a binary m x n matrix grid. A corner rectangle is defined as a set of four 1s in the grid that form the corners of an axis-aligned rectangle. Importantly, only the corners need to be 1; the interior cells can be 0.

leetcodemediumarraymathdynamic-programmingmatrix

LeetCode Problem 750

Difficulty: 🟡 Medium
Topics: Array, Math, Dynamic Programming, Matrix

Solution

Problem Understanding

The problem asks us to count the number of corner rectangles in a binary m x n matrix grid. A corner rectangle is defined as a set of four 1s in the grid that form the corners of an axis-aligned rectangle. Importantly, only the corners need to be 1; the interior cells can be 0. The four 1s must be distinct, so rectangles with overlapping corners do not count multiple times unless they form distinct sets of four 1s.

The input grid is a 2D array containing only 0s and 1s. The output is a single integer representing the number of distinct corner rectangles.

Constraints provide insight into the problem scale. The matrix can be up to 200 x 200, which makes O(m^2 * n^2) algorithms potentially infeasible, while the total number of 1s is limited to 6000, which allows algorithms that depend on the number of 1s rather than the total grid size.

Edge cases include grids with a single row or column, which cannot form rectangles, grids full of 1s, or sparse grids with very few 1s scattered across many rows and columns.

Approaches

The brute-force approach would iterate over all pairs of rows and all pairs of columns, checking whether all four corners are 1. Specifically, for every pair of rows (r1, r2) and every pair of columns (c1, c2), we check if grid[r1][c1], grid[r1][c2], grid[r2][c1], and grid[r2][c2] are all 1. While correct, this approach has time complexity O(m^2 * n^2) and becomes infeasible for the largest allowed grid sizes.

The optimal approach relies on a key observation: for any pair of rows, the problem reduces to counting pairs of columns where both rows have 1s. If row i and row j both have 1s in columns c1 and c2, then (i, j, c1, c2) forms a corner rectangle. This allows us to iterate over all pairs of rows and maintain a count of shared 1 columns, adding count * (count - 1) / 2 rectangles for each new shared 1. This approach reduces the problem to O(m^2 * n) time and O(n^2) space in the worst case.

Approach Time Complexity Space Complexity Notes
Brute Force O(m^2 * n^2) O(1) Check every combination of row and column pairs
Optimal O(m^2 * n) O(n^2) Count shared 1s between row pairs and calculate rectangles combinatorially

Algorithm Walkthrough

  1. Initialize a variable result to zero. This will accumulate the total number of corner rectangles.
  2. Iterate over all pairs of rows (r1, r2) using a nested loop.
  3. For each pair (r1, r2), iterate through all columns c and count how many columns have 1 in both r1 and r2. Let this count be shared.
  4. The number of rectangles formed by these two rows and the shared columns is shared * (shared - 1) / 2. Add this value to result.
  5. After processing all pairs of rows, return result.

Why it works: The invariant is that for any two rows, each pair of columns with 1s in both rows uniquely defines a rectangle. Counting all pairs of shared columns ensures that all possible rectangles are considered without double-counting.

Python Solution

from typing import List

class Solution:
    def countCornerRectangles(self, grid: List[List[int]]) -> int:
        m, n = len(grid), len(grid[0])
        result = 0
        for r1 in range(m):
            for r2 in range(r1 + 1, m):
                shared = 0
                for c in range(n):
                    if grid[r1][c] == 1 and grid[r2][c] == 1:
                        shared += 1
                result += shared * (shared - 1) // 2
        return result

The Python implementation first calculates the number of rows m and columns n. It iterates through all pairs of rows (r1, r2), then counts the columns where both rows have 1s. Using the combinatorial formula shared * (shared - 1) // 2, it calculates the number of rectangles formed by that row pair and adds it to result. Finally, it returns the total count.

Go Solution

func countCornerRectangles(grid [][]int) int {
    m, n := len(grid), len(grid[0])
    result := 0
    for r1 := 0; r1 < m; r1++ {
        for r2 := r1 + 1; r2 < m; r2++ {
            shared := 0
            for c := 0; c < n; c++ {
                if grid[r1][c] == 1 && grid[r2][c] == 1 {
                    shared++
                }
            }
            result += shared * (shared - 1) / 2
        }
    }
    return result
}

The Go version mirrors the Python logic, using integer division for the combinatorial calculation. Go requires explicit type handling for slices but otherwise works the same way.

Worked Examples

Example 1

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

For row pairs (1,3), shared columns with 1s are [2, 4]. Count = 2, rectangles = 2 * 1 / 2 = 1. Result = 1.

Example 2

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

For each row pair, all columns have 1s. For row pair (0,1), shared = 3, rectangles = 3 * 2 / 2 = 3. (0,2) = 3, (1,2) = 3. Total = 9.

Example 3

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

Only one row exists, so no row pairs. Result = 0.

Complexity Analysis

Measure Complexity Explanation
Time O(m^2 * n) Iterate through all pairs of rows and all columns for each pair
Space O(1) Only a few integer variables are used

The time complexity is dominated by the nested row loop and column check, while the space complexity is constant because no additional data structures proportional to input size are used.

Test Cases

# Provided examples
assert Solution().countCornerRectangles([[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]) == 1  # single rectangle
assert Solution().countCornerRectangles([[1,1,1],[1,1,1],[1,1,1]]) == 9  # multiple rectangles
assert Solution().countCornerRectangles([[1,1,1,1]]) == 0  # only one row

# Edge cases
assert Solution().countCornerRectangles([[1]]) == 0  # single cell
assert Solution().countCornerRectangles([[0,0],[0,0]]) == 0  # no 1s
assert Solution().countCornerRectangles([[1,0],[0,1]]) == 0  # no rectangle possible
assert Solution().countCornerRectangles([[1,1],[1,1]]) == 1  # smallest rectangle
Test Why
Single rectangle Validates simple case with one rectangle
Multiple rectangles Validates counting multiple rectangles in dense grids
Single row Cannot form rectangles, tests minimum row constraint
Single cell Cannot form rectangles, tests smallest grid
No 1s Grid with zeros only, tests absence of rectangles
Sparse 1s Ensure algorithm ignores non-corner patterns
Smallest rectangle Confirms algorithm detects minimal rectangle

Edge Cases

One important edge case is a grid with only a single row or a single column. Rectangles cannot form because at least two rows and two columns are required. The implementation naturally handles this by iterating over row pairs, which will not exist in a single-row grid.

Another edge case is a fully dense grid where every element is 1. This tests that the combinatorial counting works correctly and that the algorithm does not double-count rectangles. Each row pair will correctly calculate shared * (shared - 1) / 2 for the number of rectangles.

A third edge case is sparse grids with 1s scattered in such a way that some row pairs have no shared 1s. The algorithm correctly adds zero rectangles in these cases, preventing overcounting. This ensures correctness even when most of the matrix is 0.