---
# System prepended metadata

title: LC 3128. Right Triangles
tags: [medium, leedcode, c++]

---

# 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:** 
![image](https://hackmd.io/_uploads/rJB4Bwsb0.png)
Input: grid = [[0,1,0],[0,1,1],[0,1,0]]

Output: 2

Explanation:

There are two right triangles.

**Example 2:** 
![image](https://hackmd.io/_uploads/rJLHHDj-A.png)
Input: grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]

Output: 0

Explanation:

There are no right triangles.

**Example 3:** 
![image](https://hackmd.io/_uploads/HJuUSPiWR.png)
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++
```cpp=
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
