We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Number Of Corner Rectangles

Number: 751

Difficulty: Medium

Paid? Yes

Companies: Meta

Problem Description

Given an m x n binary matrix, count the number of corner rectangles. A corner rectangle is defined as a group of four distinct 1’s that form the corners of an axis-aligned rectangle in the grid. Note that only the corners need to have the value 1.

Key Insights

  • Only the four corner positions need to be 1, and the rectangle edges are aligned with the axes.
  • Instead of checking every possible rectangle, iterate over pairs of rows.
  • For every pair of rows, count the columns where both rows have a 1.
  • If there are k columns with 1’s in both rows, there are k choose 2 possible rectangles using that row pair.
  • The problem reduces to summing k*(k-1)/2 over all row pairs.

Space and Time Complexity

Time Complexity: O(m^2 * n)
Space Complexity: O(1)

Solution

The solution leverages the insight that a valid rectangle is determined by a pair of rows that share at least two columns containing 1’s. For each pair of rows, traverse every column to count the columns in which both rows have a 1. With k such columns, the number of rectangles formed is given by the combination formula k * (k - 1) / 2. Sum the rectangles from all row pairs to obtain the total count.

Code Solutions

# Function to count the number of corner rectangles in the grid
def countCornerRectangles(grid):
    rows = len(grid)                   # Number of rows in the grid
    cols = len(grid[0])                # Number of columns in the grid
    rectangle_count = 0                # Initialize the count of rectangles
    
    # Iterate over all pairs of rows (i, j) where i < j
    for i in range(rows):
        for j in range(i + 1, rows):
            common_ones = 0            # Counter for columns with common 1's in both rows
            # Check every column for a common 1 in both rows
            for col in range(cols):
                if grid[i][col] == 1 and grid[j][col] == 1:
                    common_ones += 1
            # For k common ones, number of rectangles is combination k choose 2
            if common_ones >= 2:
                rectangle_count += common_ones * (common_ones - 1) // 2
    return rectangle_count

# Example usage:
grid = [[1,0,0,1,0],
        [0,0,1,0,1],
        [0,0,0,1,0],
        [1,0,1,0,1]]
print(countCornerRectangles(grid))  # Output: 1
← Back to All Questions