# LC 3128. Right Triangles

### [Problem link](https://leetcode.com/problems/right-triangles/)

###### tags: `leedcode` `medium` `c++`

You are given a 2D boolean matrix <code>grid</code>.

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

**Note:**

- A collection of 3 elements of <code>grid</code> is a **right triangle** if one of its elements is in the **same row** with another<!-- notionvc: 6133ebe2-45aa-4346-9c28-03193b794c49 --> element and in the **same column** with the third element. The 3 elements do not have to be next to each other.

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

Output: 2

Explanation:

There are two right triangles.

**Example 2:**
Input: grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]

Output: 0

Explanation:

There are no right triangles.

**Example 3:**
Input:grid = [[1,0,1],[1,0,0],[1,0,0]]

Output:2

Explanation:

There are two right triangles.

**Constraints:**

- <code>1 <= grid.length <= 1000</code>
- <code>1 <= grid[i].length <= 1000</code>
- <code>0 <= grid[i][j] <= 1</code>

## Solution 1
#### C++

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

>### Complexity
>m = grid.length
>n = grid[i].length
>| | Time Complexity | Space Complexity |
>| ----------- | --------------- | ---------------- |
>| Solution 1 | O(mn) | O(m + n) |

## Note
x