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.
- Difficulty: Medium
- Topics: Arrays, Dynamic Programming, Math, 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.lengthn == grid[i].length1 <= m, n <= 200grid[i][j] is 0 or 1The number of 1s in the grid is at most 6000.
Hints for Number of Corner Rectangles
Hint 1
A rectangle is decided by a pair of rows and a pair of columns.
Hint 2
Fix the pair of columns; then count the rows that hold a
1in both.Hint 3
If
krows share a column pair, they contributek · (k - 1) / 2rectangles.
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 with1in 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 ansJava
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