Problem Description

You are given a 2D matrix grid of size m x n where each cell contains either 0 or 1. Your task is to count the number of corner rectangles that can be formed in this grid.

A corner rectangle is defined as a rectangle where:

• All four corners of the rectangle have the value 1
• The rectangle is axis-aligned (its sides are parallel to the grid's rows and columns)
• The four corner cells must be distinct (different positions in the grid)
• Only the corners need to be 1 - the edges and interior can be either 0 or 1

For example, if you have four 1s at positions (r1, c1), (r1, c2), (r2, c1), and (r2, c2) where r1 < r2 and c1 < c2, these form a valid corner rectangle.

The solution uses a hash table approach where it processes the grid row by row. For each row, it finds all pairs of columns (i, j) where both positions contain 1. The hash table keeps track of how many previous rows have 1s at the same column pair (i, j). When processing a new row with 1s at columns i and j, the count in the hash table tells us how many rectangles can be formed with the current row as the bottom edge and one of the previous rows as the top edge. After counting, the current pair is added to the hash table for future rows to reference.

Intuition

To count corner rectangles, we need to find all possible combinations of four 1s that form rectangle corners. A naive approach would be to check all possible combinations of four cells, but this would be extremely inefficient with time complexity of O(m^2 * n^2) or worse.

Let's think about what defines a rectangle: we need two rows and two columns. If we fix two rows r1 and r2, then for these rows to form rectangles, we need to find column pairs (i, j) where both rows have 1s at columns i and j.

This observation leads to a key insight: instead of looking for four corners at once, we can break down the problem by processing rows sequentially. For any row we're currently examining, we can ask: "How many rectangles can I form where this row is the bottom edge?"

To answer this, we need to know how many previous rows have the same pattern of column pairs with 1s. If the current row has 1s at columns i and j, and we've seen k previous rows that also have 1s at columns i and j, then we can form k rectangles using the current row as the bottom edge (each of those k previous rows can serve as the top edge).

This naturally suggests using a hash table where the key is a column pair (i, j) and the value is the count of rows we've seen so far that have 1s at both columns i and j. As we process each row:

1. For every pair of 1s in the current row at columns (i, j), we check our hash table to see how many rectangles we can form
2. We then increment the count for this column pair in our hash table for future rows to use

This approach is efficient because we only iterate through each row once and for each row we only consider pairs of columns that actually contain 1s, avoiding unnecessary checks.

Learn more about Math and Dynamic Programming patterns.

Solution Approach

The implementation uses a hash table combined with row-by-row enumeration to efficiently count corner rectangles.

Data Structure:

• cnt: A Counter (hash table) that stores column pairs as keys (i, j) and their occurrence count across previous rows as values
• ans: Running total of corner rectangles found

Algorithm Steps:

1. Initialize variables:

   • ans = 0 to store the total count of rectangles
   • cnt = Counter() to track column pairs
   • n = len(grid[0]) to get the number of columns

2. Process each row sequentially:

   for row in grid:

   Each row will potentially serve as the bottom edge of rectangles.

3. Find all pairs of 1s in the current row:

   for i, c1 in enumerate(row):
       if c1:  # If column i has a 1
           for j in range(i + 1, n):
               if row[j]:  # If column j also has a 1

   We iterate through all column positions. When we find a 1 at column i, we look for all 1s at columns j > i to form valid column pairs.

4. Count rectangles using the current column pair:

   ans += cnt[(i, j)]

   The value cnt[(i, j)] tells us how many previous rows have 1s at both columns i and j. Each such row can form a rectangle with the current row, so we add this count to our answer.

5. Update the hash table:

   cnt[(i, j)] += 1

   After counting, we increment the count for this column pair (i, j) in the hash table, as the current row can now be used as a top edge for future rectangles.

Time Complexity: O(m * n^2) where m is the number of rows and n is the number of columns. For each row, we potentially examine all O(n^2) column pairs.

Space Complexity: O(n^2) for storing at most n * (n-1) / 2 column pairs in the hash table.

The elegance of this solution lies in its incremental nature - by processing rows one at a time and maintaining a running count of column pair patterns, we avoid redundant computations and achieve an efficient solution.

Example Walkthrough

Let's walk through a small example to illustrate how the hash table approach counts corner rectangles.

Consider this 4×3 grid:

grid = [
  [1, 1, 1],  # row 0
  [1, 0, 1],  # row 1
  [0, 1, 1],  # row 2
  [1, 1, 0]   # row 3
]

Initial State:

• ans = 0 (rectangle count)
• cnt = {} (empty hash table for column pairs)

Processing Row 0: [1, 1, 1]

Find all pairs of 1s:

• Columns (0,1): both have 1s → ans += cnt[(0,1)] = 0, then cnt[(0,1)] = 1
• Columns (0,2): both have 1s → ans += cnt[(0,2)] = 0, then cnt[(0,2)] = 1
• Columns (1,2): both have 1s → ans += cnt[(1,2)] = 0, then cnt[(1,2)] = 1

State after row 0: ans = 0, cnt = {(0,1): 1, (0,2): 1, (1,2): 1}

Processing Row 1: [1, 0, 1]

Find all pairs of 1s:

• Columns (0,2): both have 1s → ans += cnt[(0,2)] = 1 (forms 1 rectangle with row 0!), then cnt[(0,2)] = 2

The rectangle formed has corners at: (0,0), (0,2), (1,0), (1,2)

State after row 1: ans = 1, cnt = {(0,1): 1, (0,2): 2, (1,2): 1}

Processing Row 2: [0, 1, 1]

Find all pairs of 1s:

• Columns (1,2): both have 1s → ans += cnt[(1,2)] = 1 (forms 1 rectangle with row 0!), then cnt[(1,2)] = 2

The rectangle formed has corners at: (0,1), (0,2), (2,1), (2,2)

State after row 2: ans = 2, cnt = {(0,1): 1, (0,2): 2, (1,2): 2}

Processing Row 3: [1, 1, 0]

Find all pairs of 1s:

• Columns (0,1): both have 1s → ans += cnt[(0,1)] = 1 (forms 1 rectangle with row 0!), then cnt[(0,1)] = 2

The rectangle formed has corners at: (0,0), (0,1), (3,0), (3,1)

Final Result: ans = 3

The three corner rectangles found are:

1. Corners at (0,0), (0,2), (1,0), (1,2)
2. Corners at (0,1), (0,2), (2,1), (2,2)
3. Corners at (0,0), (0,1), (3,0), (3,1)

Notice how the hash table efficiently tracks which column pairs have appeared in previous rows, allowing us to instantly count how many rectangles can be formed when we encounter the same column pair in a new row.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n²)

The algorithm iterates through each row of the grid (m rows total). For each row, it uses two nested loops to examine all pairs of columns where both positions contain 1s. In the worst case where a row contains all 1s, we examine n × (n-1) / 2 pairs, which is O(n²). Since we do this for all m rows, the overall time complexity is O(m × n²).

Space Complexity: O(n²)

The space is dominated by the cnt Counter dictionary, which stores counts for column pairs (i, j). In the worst case, we could have entries for all possible column pairs. The number of unique column pairs is n × (n-1) / 2, which is O(n²). Each entry stores a tuple of two integers as the key and an integer count as the value, but the number of entries determines the space complexity, giving us O(n²).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Incorrect Column Pair Ordering

A common mistake is not maintaining consistent ordering when creating column pairs as hash table keys. If you accidentally create both (i, j) and (j, i) for the same pair of columns, they'll be treated as different keys in the hash table, leading to incorrect counts.

Incorrect Implementation:

# WRONG: Might create both (2, 5) and (5, 2) as separate keys
for col_i in range(num_columns):
    if row[col_i] == 1:
        for col_j in range(num_columns):  # Should start from col_i + 1
            if col_i != col_j and row[col_j] == 1:
                column_pair = (col_i, col_j)  # Might be (5, 2) in one iteration

Correct Implementation:

# RIGHT: Always maintains col_i < col_j ordering
for col_i in range(num_columns):
    if row[col_i] == 1:
        for col_j in range(col_i + 1, num_columns):  # Ensures col_j > col_i
            if row[col_j] == 1:
                column_pair = (col_i, col_j)  # Always (smaller, larger)

2. Counting Rectangles Before Updating the Hash Table

The order of operations matters. You must count rectangles using the current hash table value before incrementing it. Reversing this order will include the current row in its own rectangle count.

Incorrect Implementation:

# WRONG: Updates counter before using it
if column_pair in column_pair_counts:
    column_pair_counts[column_pair] += 1  # Increment first
    result += column_pair_counts[column_pair]  # Then add (wrong count!)
else:
    column_pair_counts[column_pair] = 1

Correct Implementation:

# RIGHT: Uses counter value before updating
if column_pair in column_pair_counts:
    result += column_pair_counts[column_pair]  # Add current count first
    column_pair_counts[column_pair] += 1  # Then increment for future
else:
    column_pair_counts[column_pair] = 1

3. Inefficient Checking for 1s

Processing all column pairs even when one or both positions contain 0 wastes computation time.

Inefficient Implementation:

# INEFFICIENT: Checks all pairs, then filters
for col_i in range(num_columns):
    for col_j in range(col_i + 1, num_columns):
        if row[col_i] == 1 and row[col_j] == 1:  # Check inside nested loop
            # Process pair

Efficient Implementation:

# EFFICIENT: Early termination when encountering 0s
for col_i in range(num_columns):
    if row[col_i] == 0:  # Skip early if first column is 0
        continue
    for col_j in range(col_i + 1, num_columns):
        if row[col_j] == 0:  # Skip if second column is 0
            continue
        # Process pair (both are guaranteed to be 1)

4. Using Mutable Objects as Hash Keys

Using lists instead of tuples for column pairs will cause errors since lists aren't hashable.

Incorrect:

column_pair = [col_i, col_j]  # Lists are mutable and unhashable
column_pair_counts[column_pair] += 1  # TypeError!

Correct:

column_pair = (col_i, col_j)  # Tuples are immutable and hashable
column_pair_counts[column_pair] += 1  # Works correctly