Number of Corner Rectangles — Medium Problem & Solution

Given a binary grid, count the corner rectangles: four distinct cells holding 1 that form the corners of an axis-aligned rectangle.

Difficulty: Medium
Topics: Arrays, Math, Dynamic Programming, Matrix
Asked at: Amazon, Google, Meta
Time limit: 2 s
Memory limit: 256 MB
Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given a binary grid, count the corner rectangles: four distinct cells holding 1 that form the corners of an axis-aligned rectangle. The rectangle must have positive width and height, but the cells in between may hold anything.

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: Only one set of four 1s lines up as corners.

Example 2

Input: grid = [[1,1,1],[1,1,1],[1,1,1]]
Output: 9
Explanation: Three column pairs, each shared by three row pairs.

Example 3

Input: grid = [[1,1,1,1]]
Output: 0
Explanation: A single row cannot give a rectangle any height.

Constraints

m == grid.length
n == grid[i].length
1 <= m, n <= 200
grid[i][j] is 0 or 1
The number of 1s in the grid is at most 6000.

How to solve Number of Corner Rectangles

Every rectangle is determined by two columns and two rows. Sweep the rows, and for each pair of columns that the current row fills, add the number of earlier rows that also filled that pair.

Approach

Keep a table seen[j1][j2] counting the rows processed so far with 1 in both columns.
For each row, enumerate every pair (j1 < j2) of its 1-columns.
Add seen[j1][j2] to the answer, then increment it.

Why it works

Adding before incrementing pairs the current row with each earlier row exactly once, so each rectangle is counted from its bottom row alone — no factor-of-two correction and no double counting. The running sum is the same k · (k - 1) / 2 the hint describes, accumulated incrementally.

Complexity

Time — O(m · n²) in the worst case, and O(Σ ones_per_row²) in practice
Space — O(n²)

Pitfalls

Counting each rectangle from both of its rows doubles the answer.
The pair must be ordered (j1 < j2) or every rectangle is counted twice again.
Enumerating all four corners directly is O(m² · n²) and far too slow.

Reference solution

Python

from typing import List

def countCornerRectangles(grid: List[List[int]]) -> int:
    n = len(grid[0])
    seen = [[0] * n for _ in range(n)]
    ans = 0
    for row in grid:
        ones = [j for j in range(n) if row[j] == 1]
        for a in range(len(ones)):
            for b in range(a + 1, len(ones)):
                j1, j2 = ones[a], ones[b]
                ans += seen[j1][j2]
                seen[j1][j2] += 1
    return ans

JavaScript

var countCornerRectangles = function(grid) {
    var m = grid.length, n = grid[0].length, i, j;
    var seen = [];
    for (i = 0; i < n; i++) {
        var row = [];
        for (j = 0; j < n; j++) row.push(0);
        seen.push(row);
    }
    var ans = 0;
    for (i = 0; i < m; i++) {
        for (var j1 = 0; j1 < n; j1++) {
            if (grid[i][j1] !== 1) continue;
            for (var j2 = j1 + 1; j2 < n; j2++) {
                if (grid[i][j2] !== 1) continue;
                ans += seen[j1][j2];
                seen[j1][j2]++;
            }
        }
    }
    return ans;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 667 arrays problems · the whole catalogue