3128. Right Triangles

Posted on Edited on In

3128. Right Triangles

Description

You are given a 2D boolean matrix grid.

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

Note:

  • 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 do not have to be next to each other.

Example 1:

010
011
010
010
011
010
1
2
3
4
5
6
7
Input: grid = [[0,1,0],[0,1,1],[0,1,0]]

Output: 2

Explanation:

There are two right triangles.

Example 2:

1000
0101
1000
1
2
3
4
5
6
7
Input: grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]

Output: 0

Explanation:

There are no right triangles.

Example 3:

101
100
100
101
100
100
1
2
3
4
5
6
7
Input: grid = [[1,0,1],[1,0,0],[1,0,0]]

Output:2

Explanation:

There are two right triangles.

Constraints:

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

Hints/Notes

  • N/A

Solution

Language: C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
public:
    long long numberOfRightTriangles(vector<vector<int>>& grid) {
        int numRows = grid.size();
        int numColumns = grid[0].size();
        vector<int> rows(numRows, 0);
        vector<int> colomns(numColumns, 0);
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numColumns; j++) {
                if (grid[i][j] == 1) {
                    rows[i]++;
                    colomns[j]++;
                }
            }
        }
        long long res = 0;
        for (int i = 0; i < numRows; i++) {
            for (int j = 0; j < numColumns; j++) {
                if (grid[i][j] == 1) {
                    res += (rows[i] - 1) * (colomns[j] - 1);
                }
            }
        }
        return res;
    }
};