Problem Description

You are given a 2D binary matrix grid of size m x n (where each cell is either 0 or 1). A corner rectangle is defined as a set of four distinct cells with value 1 that form the four corners of a rectangle whose sides are parallel to the rows and columns of the grid. Your task is to count the total number of such corner rectangles in the given matrix.

• Each rectangle must use four 1 cells as its corners.
• Rectangles must have sides aligned with the grid (no diagonals).
• You may not reuse a cell in the same rectangle, but rectangles may overlap or share cells across different rectangles.
• grid[i][j] is either 0 or 1.

Example:
Input: grid = [[1,0,0,1,0],[0,0,1,0,1],[0,0,0,1,0],[1,0,1,0,1]]
Output: 1
(There is only one rectangle whose four corners are all 1.)

Thought Process

The straightforward way to solve this problem is to check every possible combination of four 1s in the grid and see if they form a rectangle. However, this approach is very inefficient because the number of combinations can be huge, especially for large grids.

To optimize, we observe that a rectangle is uniquely determined by two rows and two columns where all four intersection points are 1. Therefore, instead of checking every quadruple, we can focus on pairs of rows and look for columns where both rows have a 1. Each pair of such columns in the same two rows forms a rectangle.

The key insight is: for every pair of rows, count the number of columns where both have 1s; for every pair of such columns, a rectangle can be formed.

Solution Approach

• Step 1: Iterate over all pairs of rows in the grid. For each pair, we want to find columns where both rows have a 1.
• Step 2: For each pair of rows, scan through all columns. If both rows have a 1 in the same column, increment a counter for that pair of rows.
• Step 3: If there are k columns where both rows have a 1, then the number of rectangles that can be formed using these two rows and any two of these columns is k * (k-1) / 2 (since choosing any 2 columns out of k forms a rectangle).
• Step 4: Sum up the number of rectangles for all pairs of rows.

This approach is much more efficient than brute force, as it reduces the problem to counting pairs of columns for each row pair.

Example Walkthrough

Consider the following grid:

    1 0 0 1 0
    0 0 1 0 1
    0 0 0 1 0
    1 0 1 0 1
  

• Pair rows 0 and 3: Both have 1s at columns 0 and 3. So, columns [0, 3] are shared. Number of rectangles = 1 (choose columns 0 and 3).
• All other row pairs either do not have at least two columns with 1s in both rows, or have only one such column (which can't form a rectangle).
• So, the total number of rectangles is 1.

Time and Space Complexity

• Brute-force approach: Would involve checking all quadruples of 1s, leading to O((mn)^2) time complexity (very slow).
• Optimized approach: For each pair of rows (O(m^2)), we scan all columns (O(n)), so the total time is O(m^2 * n). For moderate grid sizes (e.g., m and n up to 200), this is feasible.
• Space complexity: Only O(1) extra space is needed (or O(n) if you store temporary arrays for columns).

Summary

The problem is elegantly solved by shifting perspective from checking all possible rectangles to counting shared columns of 1s between row pairs. By leveraging combinatorics (number of ways to choose 2 columns out of k), we efficiently count rectangles without redundant checks. This approach is both simple to implement and highly performant for typical grid sizes.

Code Implementation

class Solution:
    def countCornerRectangles(self, grid):
        if not grid or not grid[0]:
            return 0
        m, n = len(grid), len(grid[0])
        ans = 0
        for i in range(m):
            for j in range(i+1, m):
                count = 0
                for k in range(n):
                    if grid[i][k] == 1 and grid[j][k] == 1:
                        count += 1
                if count >= 2:
                    ans += count * (count - 1) // 2
        return ans
      

class Solution {
public:
    int countCornerRectangles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                int count = 0;
                for (int k = 0; k < n; ++k) {
                    if (grid[i][k] == 1 && grid[j][k] == 1) {
                        count++;
                    }
                }
                if (count >= 2) {
                    ans += count * (count - 1) / 2;
                }
            }
        }
        return ans;
    }
};
      

class Solution {
    public int countCornerRectangles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int ans = 0;
        for (int i = 0; i < m; ++i) {
            for (int j = i + 1; j < m; ++j) {
                int count = 0;
                for (int k = 0; k < n; ++k) {
                    if (grid[i][k] == 1 && grid[j][k] == 1) {
                        count++;
                    }
                }
                if (count >= 2) {
                    ans += count * (count - 1) / 2;
                }
            }
        }
        return ans;
    }
}
      

var countCornerRectangles = function(grid) {
    const m = grid.length, n = grid[0].length;
    let ans = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = i + 1; j < m; ++j) {
            let count = 0;
            for (let k = 0; k < n; ++k) {
                if (grid[i][k] === 1 && grid[j][k] === 1) {
                    count++;
                }
            }
            if (count >= 2) {
                ans += count * (count - 1) / 2;
            }
        }
    }
    return ans;
};