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