Problem Description

You have a 2D boolean matrix grid filled with 0s and 1s.

A right triangle is formed by selecting 3 elements from the grid that all have value 1, where:

• One element serves as the right angle vertex
• One element is in the same row as the right angle vertex
• One element is in the same column as the right angle vertex
• The 3 elements don't need to be adjacent to each other

Your task is to count how many such right triangles can be formed using the 1s in the grid.

For example, if you have a 1 at position (i, j) that serves as the right angle, you can form a right triangle with any other 1 in row i and any other 1 in column j. If there are r total 1s in row i and c total 1s in column j, then this position can form (r-1) × (c-1) right triangles (excluding the position itself from both counts).

The solution counts the number of 1s in each row and column first, then for each 1 in the grid, calculates how many right triangles can be formed with that 1 as the right angle vertex.

Intuition

The key insight is recognizing that every right triangle in the grid must have one vertex serving as the "corner" or right angle, with the other two vertices sharing either a row or column with this corner vertex.

Instead of checking all possible combinations of three 1s in the grid (which would be computationally expensive), we can think about it from the perspective of each potential right angle vertex. For any 1 in the grid at position (i, j), it can serve as the right angle of a triangle if:

• There's at least one other 1 in the same row i
• There's at least one other 1 in the same column j

If we know how many 1s are in row i and column j, we can use the multiplication principle from combinatorics. If there are rows[i] total 1s in row i and cols[j] total 1s in column j, then:

• We have rows[i] - 1 choices for the horizontal vertex (excluding the corner itself)
• We have cols[j] - 1 choices for the vertical vertex (excluding the corner itself)
• Total triangles with this corner = (rows[i] - 1) × (cols[j] - 1)

This leads us to a two-pass approach:

1. First pass: Count the number of 1s in each row and column
2. Second pass: For each 1, calculate how many triangles it can form as a right angle vertex

This approach is efficient because we only need to traverse the grid twice, giving us O(m × n) time complexity, where m and n are the dimensions of the grid.

Learn more about Math and Combinatorics patterns.

Solution Approach

The implementation follows a counting and enumeration strategy:

Step 1: Count 1s in each row and column

We initialize two arrays:

• rows: An array of size len(grid) to store the count of 1s in each row
• cols: An array of size len(grid[0]) to store the count of 1s in each column

We traverse the entire grid once, and for each cell (i, j) that contains a 1, we increment both rows[i] and cols[j]:

for i, row in enumerate(grid):
    for j, x in enumerate(row):
        rows[i] += x  # x is either 0 or 1
        cols[j] += x

Step 2: Calculate the number of right triangles

We traverse the grid again, and for each cell (i, j) that contains a 1, we treat it as the right angle vertex of potential triangles:

ans = 0
for i, row in enumerate(grid):
    for j, x in enumerate(row):
        if x:  # if current cell is 1
            ans += (rows[i] - 1) * (cols[j] - 1)

The formula (rows[i] - 1) * (cols[j] - 1) calculates:

• rows[i] - 1: Number of other 1s in the same row (excluding the current cell)
• cols[j] - 1: Number of other 1s in the same column (excluding the current cell)
• Their product gives us the total number of valid right triangles with the current cell as the right angle

Time Complexity: O(m × n) where m and n are the dimensions of the grid, as we traverse the grid twice.

Space Complexity: O(m + n) for storing the row and column counts.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Consider this 3×4 grid:

grid = [[0, 1, 0, 1],
        [1, 1, 1, 0],
        [1, 0, 0, 1]]

Step 1: Count 1s in each row and column

First, we count how many 1s are in each row and column:

• Row 0: Contains 1s at positions (0,1) and (0,3) → rows[0] = 2

• Row 1: Contains 1s at positions (1,0), (1,1), and (1,2) → rows[1] = 3

• Row 2: Contains 1s at positions (2,0) and (2,3) → rows[2] = 2

• Column 0: Contains 1s at positions (1,0) and (2,0) → cols[0] = 2

• Column 1: Contains 1s at positions (0,1) and (1,1) → cols[1] = 2

• Column 2: Contains 1s at position (1,2) → cols[2] = 1

• Column 3: Contains 1s at positions (0,3) and (2,3) → cols[3] = 2

So we have: rows = [2, 3, 2] and cols = [2, 2, 1, 2]

Step 2: Calculate triangles for each 1 as the right angle vertex

Now we visit each 1 in the grid and calculate how many triangles it can form:

• Position (0,1): (rows[0]-1) × (cols[1]-1) = (2-1) × (2-1) = 1 × 1 = 1 triangle

  • This forms a triangle with vertices at (0,1), (0,3), and (1,1)

• Position (0,3): (rows[0]-1) × (cols[3]-1) = (2-1) × (2-1) = 1 × 1 = 1 triangle

  • This forms a triangle with vertices at (0,3), (0,1), and (2,3)

• Position (1,0): (rows[1]-1) × (cols[0]-1) = (3-1) × (2-1) = 2 × 1 = 2 triangles

  • Triangle 1: vertices at (1,0), (1,1), and (2,0)
  • Triangle 2: vertices at (1,0), (1,2), and (2,0)

• Position (1,1): (rows[1]-1) × (cols[1]-1) = (3-1) × (2-1) = 2 × 1 = 2 triangles

  • Triangle 1: vertices at (1,1), (1,0), and (0,1)
  • Triangle 2: vertices at (1,1), (1,2), and (0,1)

• Position (1,2): (rows[1]-1) × (cols[2]-1) = (3-1) × (1-1) = 2 × 0 = 0 triangles

  • No triangles possible (no other 1s in column 2)

• Position (2,0): (rows[2]-1) × (cols[0]-1) = (2-1) × (2-1) = 1 × 1 = 1 triangle

  • This forms a triangle with vertices at (2,0), (2,3), and (1,0)

• Position (2,3): (rows[2]-1) × (cols[3]-1) = (2-1) × (2-1) = 1 × 1 = 1 triangle

  • This forms a triangle with vertices at (2,3), (2,0), and (0,3)

Total triangles: 1 + 1 + 2 + 2 + 0 + 1 + 1 = 8

The algorithm efficiently counts all possible right triangles by treating each 1 as a potential right angle vertex and using the multiplication principle to count valid combinations.

Solution Implementation

Time and Space Complexity

Time Complexity: O(m × n)

The algorithm consists of two main parts:

1. First nested loop: Iterates through all m × n elements in the grid to count the number of 1s in each row and column. This takes O(m × n) time.
2. Second nested loop: Again iterates through all m × n elements to calculate the number of right triangles. For each cell with value 1, it performs a constant-time calculation (rows[i] - 1) * (cols[j] - 1). This also takes O(m × n) time.

Total time complexity: O(m × n) + O(m × n) = O(m × n)

Space Complexity: O(m + n)

The algorithm uses:

• rows array of size m to store the count of 1s in each row: O(m) space
• cols array of size n to store the count of 1s in each column: O(n) space
• A few scalar variables (ans, loop indices) which take O(1) space

Total space complexity: O(m) + O(n) = O(m + n)

Where m is the number of rows and n is the number of columns in the matrix.

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

Common Pitfalls

1. Forgetting to exclude the vertex cell from counts

A common mistake is using rows[i] * cols[j] instead of (rows[i] - 1) * (cols[j] - 1). This would incorrectly count the vertex cell itself as part of the triangle's other two vertices.

Incorrect:

if grid[row_idx][col_idx] == 1:
    triangle_count += row_counts[row_idx] * col_counts[col_idx]  # Wrong!

Correct:

if grid[row_idx][col_idx] == 1:
    triangle_count += (row_counts[row_idx] - 1) * (col_counts[col_idx] - 1)

2. Not handling edge cases with insufficient 1s

When a row or column has only one 1 (the vertex itself), the formula (rows[i] - 1) * (cols[j] - 1) correctly evaluates to 0, but some might try to add explicit checks that are unnecessary and can introduce bugs:

Overcomplicated (and potentially buggy):

if grid[row_idx][col_idx] == 1:
    if row_counts[row_idx] > 1 and col_counts[col_idx] > 1:
        triangle_count += (row_counts[row_idx] - 1) * (col_counts[col_idx] - 1)
    # This check is redundant and might lead to errors if modified incorrectly

Better (simpler and cleaner):

if grid[row_idx][col_idx] == 1:
    triangle_count += (row_counts[row_idx] - 1) * (col_counts[col_idx] - 1)
    # Naturally handles the edge case since (0 * n) or (n * 0) = 0

3. Attempting to optimize with a single pass

Some might try to calculate triangles while counting, but this leads to incorrect results because you need complete row/column counts before calculating triangles:

Incorrect single-pass attempt:

triangle_count = 0
row_counts = [0] * num_rows
col_counts = [0] * num_cols

for row_idx in range(num_rows):
    for col_idx in range(num_cols):
        if grid[row_idx][col_idx] == 1:
            # This calculation uses incomplete counts!
            triangle_count += row_counts[row_idx] * col_counts[col_idx]
            row_counts[row_idx] += 1
            col_counts[col_idx] += 1

This would miss triangles because the counts are built incrementally and aren't complete when used.

4. Integer overflow in other languages

While Python handles large integers automatically, in languages like Java or C++, the multiplication (rows[i] - 1) * (cols[j] - 1) could overflow for large grids. Consider using appropriate data types:

For Java/C++:

// Use long long in C++ or long in Java for large grids
long long triangle_count = 0;
triangle_count += (long long)(row_counts[i] - 1) * (col_counts[j] - 1);