Problem Breakdown
We are given an 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 where and , all containing ‘1’.
- Inputs: A 2D list
gridof integers. Dimensions up to 200x200. Total number of ‘1’s . - 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 to check if they are ‘1’. This is or worse ( 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 first. For any specific column , if both grid[i][k] and grid[j][k] are ‘1’, then this column contributes to the vertical sides of potential rectangles between row and row .
If we find that there are columns where both rows have a ‘1’ at those positions, any pair of these columns forms a valid rectangle with our fixed rows. The number of ways to choose 2 columns out of is .
Optimal Strategy: Iterate over all pairs of rows (). For each pair, iterate through all columns () to count common ‘1’s. Sum the combinations for every row pair. This reduces complexity significantly compared to checking quadruplets directly.
Approach
- Initialize
count = 0. - Iterate over every unique pair of rows where .
- For each such pair, initialize a variable
common_colsto track how many columns have ‘1’s in both row and row . - Iterate through all column indices from to :
- If
grid[i][k] == 1ANDgrid[j][k] == 1, incrementcommon_cols.
- If
- After checking all columns for the current row pair, calculate combinations: add to
count. - Return
countafter processing all row pairs.
Complexity Analysis
- Time Complexity: . We iterate over every pair of rows ( iterations) and for each, scan the columns (). With max dimensions 200x200, operations are roughly , 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: . 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 (
r1torows-1,r2fromr1+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_countremains 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 .