Number of Corner Rectangles

Medium
916.

Number of Corner Rectangles

Number of Corner Rectangles is a medium coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.

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.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} grid
 * @return {number}
 */
var countCornerRectangles = function(grid) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Corner Rectangles — Solution in Python, Java & C++

Number of Corner Rectangles solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.

Number of Corner Rectangles is a medium coding problem on arrays, dynamic programming and math, asked in Amazon, Google and Meta interviews.

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.

Hints for Number of Corner Rectangles

  1. Hint 1

    A rectangle is decided by a pair of rows and a pair of columns.

  2. Hint 2

    Fix the pair of columns; then count the rows that hold a 1 in both.

  3. Hint 3

    If k rows share a column pair, they contribute k · (k - 1) / 2 rectangles.

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

  1. Keep a table seen[j1][j2] counting the rows processed so far with 1 in both columns.
  2. For each row, enumerate every pair (j1 < j2) of its 1-columns.
  3. 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

Java

public static int countCornerRectangles(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[][] seen = new int[n][n];
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j1 = 0; j1 < n; j1++) {
            if (grid[i][j1] != 1) continue;
            for (int j2 = j1 + 1; j2 < n; j2++) {
                if (grid[i][j2] != 1) continue;
                ans += seen[j1][j2];
                seen[j1][j2]++;
            }
        }
    }
    return ans;
}

C++

int countCornerRectangles(vector<vector<int>>& grid) {
    int m = (int) grid.size(), n = (int) grid[0].size();
    vector<vector<int>> seen(n, vector<int>(n, 0));
    int ans = 0;
    for (int i = 0; i < m; i++) {
        for (int j1 = 0; j1 < n; j1++) {
            if (grid[i][j1] != 1) continue;
            for (int j2 = j1 + 1; j2 < n; j2++) {
                if (grid[i][j2] != 1) continue;
                ans += seen[j1][j2];
                seen[j1][j2]++;
            }
        }
    }
    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#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Dynamic Programming