Problem

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.

Examples

Example 1

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


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


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


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

Solution

Method 1 - Count Ones in Rows and Columns

Intuition

For each cell with a 1, if there are other 1s in its row and column, we can form right triangles by picking one from the row and one from the column (excluding the cell itself). For each such cell, the number of right triangles is (row_ones - 1) * (col_ones - 1).

Approach

First, count the number of 1s in each row and each column. Then, for each cell with a 1, add (row_ones - 1) * (col_ones - 1) to the answer.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

#include <vector>
using namespace std;
class Solution {
public:
    long long numberOfRightTriangles(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<int> row(m, 0), col(n, 0);
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j]) { row[i]++; col[j]++; }
        long long ans = 0;
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                if (grid[i][j])
                    ans += (long long)(row[i] - 1) * (col[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

func numberOfRightTriangles(grid [][]int) int64 {
    m, n := len(grid), len(grid[0])
    row := make([]int, m)
    col := make([]int, n)
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                row[i]++
                col[j]++
            }
        }
    }
    var ans int64
    for i := 0; i < m; i++ {
        for j := 0; j < n; j++ {
            if grid[i][j] == 1 {
                ans += int64(row[i]-1) * int64(col[j]-1)
            }
        }
    }
    return ans
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    public long numberOfRightTriangles(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[] row = new int[m], col = new int[n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1) { row[i]++; col[j]++; }
        long ans = 0;
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (grid[i][j] == 1)
                    ans += (long)(row[i] - 1) * (col[j] - 1);
        return ans;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

class Solution {
    fun numberOfRightTriangles(grid: Array<IntArray>): Long {
        val m = grid.size
        val n = grid[0].size
        val row = IntArray(m)
        val col = IntArray(n)
        for (i in 0 until m) for (j in 0 until n)
            if (grid[i][j] == 1) { row[i]++; col[j]++ }
        var ans = 0L
        for (i in 0 until m) for (j in 0 until n)
            if (grid[i][j] == 1)
                ans += (row[i] - 1).toLong() * (col[j] - 1)
        return ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

class Solution:
    def numberOfRightTriangles(self, grid: list[list[int]]) -> int:
        m, n = len(grid), len(grid[0])
        row = [0] * m
        col = [0] * n
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    row[i] += 1
                    col[j] += 1
        ans = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j]:
                    ans += (row[i] - 1) * (col[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
24
25

impl Solution {
    pub fn number_of_right_triangles(grid: Vec<Vec<i32>>) -> i64 {
        let m = grid.len();
        let n = grid[0].len();
        let mut row = vec![0; m];
        let mut col = vec![0; n];
        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == 1 {
                    row[i] += 1;
                    col[j] += 1;
                }
            }
        }
        let mut ans = 0i64;
        for i in 0..m {
            for j in 0..n {
                if grid[i][j] == 1 {
                    ans += (row[i] - 1) as i64 * (col[j] - 1) as i64;
                }
            }
        }
        ans
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

function numberOfRightTriangles(grid: number[][]): number {
    const m = grid.length, n = grid[0].length;
    const row = Array(m).fill(0), col = Array(n).fill(0);
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)
            if (grid[i][j]) { row[i]++; col[j]++; }
    let ans = 0;
    for (let i = 0; i < m; i++)
        for (let j = 0; j < n; j++)
            if (grid[i][j])
                ans += (row[i] - 1) * (col[j] - 1);
    return ans;
}

Complexity

  • ⏰ Time complexity: O(mn) — for counting and iterating through the grid.
  • 🧺 Space complexity: O(m + n) — for row and column counts.