Domain 2MediumMEDIUM

Number Of Corner Rectangles

Iterate through all pairs of rows, count columns with '1' in both to find common intersections, and add the number of ways to choose 2 such columns for each row pair.

Domain: medium•Updated: 2026-08-31
#matrix#math#O(R^2 C)#O(1)

Problem Breakdown

We are given an R×CR \times C binary grid where each cell contains either 0 or 1. The goal is to count how many distinct sets of four ‘1’s form the corners of a rectangle aligned with the axes (horizontal and vertical).

Key Definitions:

  • Corner Rectangle: Four cells (r1,c1),(r1,c2),(r2,c1),(r2,c2)(r_1, c_1), (r_1, c_2), (r_2, c_1), (r_2, c_2) where r1≠r2r_1 \neq r_2 and c1≠c2c_1 \neq c_2, all containing ‘1’.
  • Inputs: A 2D list grid of integers. Dimensions up to 200x200. Total number of ‘1’s ≤6000\le 6000.
  • Outputs: An integer representing the total count of such rectangles.

Implicit Constraints & Edge Cases:

  • Rectangles must have distinct corners (no overlapping points).
  • If a row or column has fewer than two ‘1’s, it cannot contribute to any rectangle as an edge.
  • Single-row or single-column grids yield 0 rectangles because we need at least one pair of rows and one pair of columns.

Intuition

A naive brute-force approach would iterate through all possible quadruplets (r1,c1),(r1,c2),(r2,c1),(r2,c2)(r_1, c_1), (r_1, c_2), (r_2, c_1), (r_2, c_2) to check if they are ‘1’. This is O(R3C)O(R^3 C) or worse (O(Nones4)O(N_{ones}^4) depending on implementation) and will time out.

Key Insight: A rectangle is defined by two distinct rows acting as the top/bottom edges and two distinct columns acting as left/right edges. Instead of iterating over all four corners, we can fix a pair of rows (i,j)(i, j) first. For any specific column kk, if both grid[i][k] and grid[j][k] are ‘1’, then this column contributes to the vertical sides of potential rectangles between row ii and row jj.

If we find that there are KK columns where both rows have a ‘1’ at those positions, any pair of these KK columns forms a valid rectangle with our fixed rows. The number of ways to choose 2 columns out of KK is (K2)=K(K−1)2\binom{K}{2} = \frac{K(K-1)}{2}.

Optimal Strategy: Iterate over all pairs of rows (O(R2)O(R^2)). For each pair, iterate through all columns (CC) to count common ‘1’s. Sum the combinations for every row pair. This reduces complexity significantly compared to checking quadruplets directly.

Approach

  1. Initialize count = 0.
  2. Iterate over every unique pair of rows (i,j)(i, j) where 0≤i<j<R0 \le i < j < R.
  3. For each such pair, initialize a variable common_cols to track how many columns have ‘1’s in both row ii and row jj.
  4. Iterate through all column indices kk from 00 to C−1C-1:
    • If grid[i][k] == 1 AND grid[j][k] == 1, increment common_cols.
  5. After checking all columns for the current row pair, calculate combinations: add common_cols×(common_cols−1)2\frac{common\_cols \times (common\_cols - 1)}{2} to count.
  6. Return count after processing all row pairs.

Complexity Analysis

  • Time Complexity: O(R2C)O(R^2 C). We iterate over every pair of rows (R2/2R^2/2 iterations) and for each, scan the columns (CC). With max dimensions 200x200, operations are roughly 400002×200=4,000,000\frac{40000}{2} \times 200 = 4,000,000, which fits comfortably within standard time limits (typically ~1-5 seconds for Python on LeetCode), especially given the constraint that total ‘1’s is limited to 6000.
  • Space Complexity: O(1)O(1). We only use a few integer variables (count, common_cols) regardless of input size, excluding the space required to store the grid itself.

Solution

class Solution:
    def countCornerRectangles(self, grid):
        """
        Counts corner rectangles in a binary matrix.
        
        Args:
            grid (List[List[int]]): A 2D list of integers containing only 0 or 1.
            
        Returns:
            int: The number of valid corner rectangles.
        """
        if not grid or not grid[0]:
            return 0
            
        rows = len(grid)
        cols = len(grid[0])
        
        total_rectangles = 0
        
        # Iterate over all unique pairs of rows (i, j) where i < j
        for r1 in range(rows):
            for r2 in range(r1 + 1, rows):
                common_ones_count = 0
                
                # Check each column to see if both row r1 and row r2 have a '1' here
                for c in range(cols):
                    if grid[r1][c] == 1 and grid[r2][c] == 1:
                        common_ones_count += 1
                
                # If we found k columns with matching ones, any pair of these 
                # columns forms a rectangle corner set. Number of pairs is C(k, 2).
                if common_ones_count >= 2:
                    total_rectangles += (common_ones_count * (common_ones_count - 1)) // 2
                    
        return total_rectangles

# Example usage for verification
if __name__ == "__main__":
    grid = [
        [1, 0, 0, 1, 0],
        [0, 0, 1, 0, 1],
        [0, 0, 0, 1, 0],
        [1, 0, 1, 0, 1]
    ]
    print(countCornerRectangles(grid)) # Expected Output: 1
    
    grid2 = [[1, 1, 1], [1, 1, 1], [1, 1, 1]]
    print(countCornerRectangles(grid2)) # Expected Output: 9

Edge Cases Handled

  • Empty or Single Row/Column: The nested loops for row pairs (r1 to rows-1, r2 from r1+1) naturally handle cases where fewer than two rows exist (loops don’t execute, returns 0). Similarly, if columns are insufficient to form a pair of common ones, the combination math yields 0.
  • No ‘1’s in Grid: The inner condition checks for both cells being 1. If no such column exists, common_ones_count remains 0, and combinations added is 0.
  • Large Number of Rectangles (Overflow): Python handles large integers automatically, so the count will not overflow even if it exceeds 231−12^{31}-1.