# Right Triangles
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/right-triangles)
Canonical: https://scaleengineer.com/dsa/problems/right-triangles
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math), [Combinatorics](https://scaleengineer.com/dsa/patterns/combinatorics), [Counting](https://scaleengineer.com/dsa/patterns/counting)
**Data structures:** Array, Hash Table
**Companies:** [Mitsogo](https://scaleengineer.com/companies/mitsogo)
---
## Problem
You are given a 2D boolean matrix `grid`.

A collection of 3 elements of `grid` is a **right triangle** if one of its elements is in the **same row** with another element and in the **same column** with the third element. The 3 elements may **not** be next to each other.

Return an integer that is the number of **right triangles** that can be made with 3 elements of `grid` such that **all** of them have a value of 1.

**Example 1:**

| 0 | 1 | 0 |
| - | - | - |
| 0 | 1 | 1 |
| 0 | 1 | 0 |

| 0 | 1 | 0 |
| - | - | - |
| 0 | 1 | 1 |
| 0 | 1 | 0 |

| 0 | 1 | 0 |
| - | - | - |
| 0 | 1 | 1 |
| 0 | 1 | 0 |

**Input:** grid = \[\[0,1,0\],\[0,1,1\],\[0,1,0\]\]

**Output:** 2

**Explanation:**

There are two right triangles with elements of the value 1\. Notice that the blue ones do **not** form a right triangle because the 3 elements are in the same column.

**Example 2:**

| 1 | 0 | 0 | 0 |
| - | - | - | - |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 |

**Input:** grid = \[\[1,0,0,0\],\[0,1,0,1\],\[1,0,0,0\]\]

**Output:** 0

**Explanation:**

There are no right triangles with elements of the value 1\. Notice that the blue ones do **not** form a right triangle.

**Example 3:**

| 1 | 0 | 1 |
| - | - | - |
| 1 | 0 | 0 |
| 1 | 0 | 0 |

| 1 | 0 | 1 |
| - | - | - |
| 1 | 0 | 0 |
| 1 | 0 | 0 |

**Input:** grid = \[\[1,0,1\],\[1,0,0\],\[1,0,0\]\]

**Output:** 2

**Explanation:**

There are two right triangles with elements of the value 1.

**Constraints:**

* `1 <= grid.length <= 1000`
* `1 <= grid[i].length <= 1000`
* `0 <= grid[i][j] <= 1`

# Approaches
## Brute-Force Iteration
A straightforward but inefficient approach is to iterate through every cell in the grid. For each cell containing a `1`, we consider it as the potential vertex of the right angle of a triangle. Then, we count how many other `1`s exist in the same row and how many exist in the same column. The product of these two counts gives the number of right triangles that can be formed with the current cell as the corner.
**Time:** O(m * n * (m + n)), where `m` is the number of rows and `n` is the number of columns. For each of the `m * n` cells, we traverse its row (n elements) and its column (m elements). This results in a cubic time complexity in the larger dimension, which is too slow for the given constraints. · **Space:** O(1), as we only use a few variables to store counts, not dependent on the input size.
**Pros:** Simple to conceptualize and implement.; Requires no additional space.
**Cons:** Highly inefficient due to redundant calculations.; Will likely result in a 'Time Limit Exceeded' error for large grids.
### Explanation
The algorithm iterates through each cell `(i, j)` of the `m x n` grid. If `grid[i][j]` is `1`, it initiates two more loops. The first inner loop scans the entire row `i` to count other cells `(i, k)` (where `k != j`) that contain a `1`. The second inner loop scans the entire column `j` to count other cells `(l, j)` (where `l != i`) that contain a `1`. Let these counts be `row_ones` and `col_ones` respectively. The number of right triangles with `(i, j)` as the corner is `row_ones * col_ones`. This product is added to a running total. This process is repeated for every cell in the grid.

```java
class Solution {
    public long numberOfRightTriangles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;
        long count = 0;

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    long rowOnes = 0;
                    for (int k = 0; k < n; k++) {
                        if (k != j && grid[i][k] == 1) {
                            rowOnes++;
                        }
                    }

                    long colOnes = 0;
                    for (int l = 0; l < m; l++) {
                        if (l != i && grid[l][j] == 1) {
                            colOnes++;
                        }
                    }

                    count += rowOnes * colOnes;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize a counter `total_triangles` to 0.
- Get the dimensions of the grid, `m` rows and `n` columns.
- Iterate through each cell `(i, j)` from `(0, 0)` to `(m-1, n-1)`.
- If `grid[i][j]` is 0, skip to the next cell.
- If `grid[i][j]` is 1, treat it as the corner of a potential right triangle.
  - Initialize `row_ones = 0` and `col_ones = 0`.
  - Iterate through row `i` (from column 0 to `n-1`). For each cell `(i, k)` where `k != j`, if `grid[i][k]` is 1, increment `row_ones`.
  - Iterate through column `j` (from row 0 to `m-1`). For each cell `(l, j)` where `l != i`, if `grid[l][j]` is 1, increment `col_ones`.
  - Add the product `row_ones * col_ones` to `total_triangles`.
- After iterating through all cells, return `total_triangles`.

## Pre-computation of Row and Column Counts
This approach optimizes the brute-force method by eliminating redundant computations. The key observation is that for each cell `(i, j)`, the brute-force method re-calculates the number of `1`s in row `i` and column `j`. We can significantly improve performance by pre-calculating the total number of `1`s in each row and each column in a single pass.
**Time:** O(m * n), where `m` is the number of rows and `n` is the number of columns. The algorithm involves two separate passes over the grid, each taking `O(m * n)` time. This is linear with respect to the number of cells in the grid. · **Space:** O(m + n). We use two arrays to store the counts of `1`s for each row and column.
**Pros:** Optimal time complexity, making it very fast for large grids.; The logic is still relatively simple to follow.
**Cons:** Requires extra space for the count arrays, which could be a concern for extremely large (but sparse) grids, though not for the given constraints.
### Explanation
The algorithm consists of two main phases. 

First, the pre-computation phase: We create two arrays, `row_counts` of size `m` and `col_counts` of size `n`, initialized to zeros. We then iterate through the entire grid once. For each cell `(i, j)` that contains a `1`, we increment `row_counts[i]` and `col_counts[j]`. After this pass, `row_counts[i]` will hold the total number of `1`s in row `i`, and `col_counts[j]` will hold the total for column `j`.

Second, the counting phase: We iterate through the grid again. For each cell `(i, j)` where `grid[i][j]` is `1`, we can find the number of other `1`s in its row and column in constant time using our pre-computed arrays. The number of other `1`s in row `i` is `row_counts[i] - 1`, and in column `j` is `col_counts[j] - 1`. The number of right triangles with `(i, j)` as the corner is the product of these two values. We sum these products for all `1`s in the grid to get the final answer. A `long` data type should be used for the total count to prevent overflow.

```java
class Solution {
    public long numberOfRightTriangles(int[][] grid) {
        int m = grid.length;
        int n = grid[0].length;

        int[] rowCounts = new int[m];
        int[] colCounts = new int[n];

        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    rowCounts[i]++;
                    colCounts[j]++;
                }
            }
        }

        long totalTriangles = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (grid[i][j] == 1) {
                    long otherRowOnes = rowCounts[i] - 1;
                    long otherColOnes = colCounts[j] - 1;
                    if (otherRowOnes > 0 && otherColOnes > 0) {
                        totalTriangles += otherRowOnes * otherColOnes;
                    }
                }
            }
        }

        return totalTriangles;
    }
}
```
### Algorithm
- Get the dimensions of the grid, `m` rows and `n` columns.
- Create an integer array `row_counts` of size `m` and `col_counts` of size `n`, both initialized to zero.
- Iterate through the grid from `(0, 0)` to `(m-1, n-1)`. If `grid[i][j]` is 1, increment `row_counts[i]` and `col_counts[j]`.
- Initialize a long integer `total_triangles` to 0.
- Iterate through the grid again from `(0, 0)` to `(m-1, n-1)`.
- If `grid[i][j]` is 1:
  - Calculate the number of other `1`s in the same row: `other_row_ones = row_counts[i] - 1`.
  - Calculate the number of other `1`s in the same column: `other_col_ones = col_counts[j] - 1`.
  - Add the product `other_row_ones * other_col_ones` to `total_triangles`.
- Return `total_triangles`.

# Solutions
### Java

```java
class Solution {
public
  long numberOfRightTriangles(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    int[] rows = new int[m];
    int[] cols = new int[n];
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        rows[i] += grid[i][j];
        cols[j] += grid[i][j];
      }
    }
    long ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          ans += (rows[i] - 1) * (cols[j] - 1);
        }
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  long long numberOfRightTriangles(vector<vector<int>> &grid) {
    int m = grid.size(), n = grid[0].size();
    vector<int> rows(m);
    vector<int> cols(n);
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        rows[i] += grid[i][j];
        cols[j] += grid[i][j];
      }
    }
    long long ans = 0;
    for (int i = 0; i < m; ++i) {
      for (int j = 0; j < n; ++j) {
        if (grid[i][j] == 1) {
          ans += (rows[i] - 1) * (cols[j] - 1);
        }
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfRightTriangles(self, grid: List[List[int]]) -> int: rows = [0] * len(grid) cols = [0] * len(grid[0]) for i, row in enumerate(grid): for j, x in enumerate(row): rows[i] += x cols[j] += x ans = 0 for i, row in enumerate(grid): for j, x in enumerate(row): if x: ans += (rows[i] - 1) * (cols[j] - 1) return ans

```