Right triangles

Array Hash Table Math Combinatorics Counting

48.4% acceptance

Feb 23, 2026

133

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.

Solution

Rust

Time O(n²)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn number_of_right_triangles(grid: Vec<Vec<i32>>) -> i64 {
    let m = grid.len();
    let n = grid[0].len();

    let row_count: Vec<i64> = grid.iter().map(|row| row.iter().sum::<i32>() as i64).collect();
    let mut col_count = vec![0i64; n];
    for row in &grid {
      for (j, &v) in row.iter().enumerate() {
        col_count[j] += v as i64;
      }
    }

    let mut result = 0i64;
    for i in 0..m {
      for j in 0..n {
        if grid[i][j] == 1 {
          result += (row_count[i] - 1) * (col_count[j] - 1);
        }
      }
    }
    result
  }
}