Skip to content

3128. Right Triangles

Description

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

Solutions

Solution 1: Counting + Enumeration

First, we can count the number of $1$s in each row and each column, and record them in the arrays $rows$ and $cols$.

Then, we enumerate each $1$. Suppose the current $1$ is in the $i$-th row and the $j$-th column. If we take this $1$ as the right angle of a right triangle, the other two right angles are in the $i$-th row and the $j$-th column. Therefore, the number of right triangles is $(rows[i] - 1) \times (cols[j] - 1)$. We add this to the total count.

The time complexity is $O(m \times n)$, and the space complexity is $O(m + n)$. Where $m$ and $n$ are the number of rows and columns in the matrix, respectively.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
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

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
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;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
func numberOfRightTriangles(grid [][]int) (ans int64) {
    m, n := len(grid), len(grid[0])
    rows := make([]int, m)
    cols := make([]int, n)
    for i, row := range grid {
        for j, x := range row {
            rows[i] += x
            cols[j] += x
        }
    }
    for i, row := range grid {
        for j, x := range row {
            if x == 1 {
                ans += int64((rows[i] - 1) * (cols[j] - 1))
            }
        }
    }
    return
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
function numberOfRightTriangles(grid: number[][]): number {
    const m = grid.length;
    const n = grid[0].length;
    const rows: number[] = Array(m).fill(0);
    const cols: number[] = Array(n).fill(0);
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            rows[i] += grid[i][j];
            cols[j] += grid[i][j];
        }
    }
    let ans = 0;
    for (let i = 0; i < m; ++i) {
        for (let j = 0; j < n; ++j) {
            if (grid[i][j] === 1) {
                ans += (rows[i] - 1) * (cols[j] - 1);
            }
        }
    }
    return ans;
}

Comments