Scale Engineer

Right Triangles

Med
#2778Time: O(m * n * (m + n)), where `m` is the number of rows and `n` is the number of columns. For each of the `m * n` cells, we traverse its row (n elements) and its column (m elements). This results in a cubic time complexity in the larger dimension, which is too slow for the given constraints.Space: O(1), as we only use a few variables to store counts, not dependent on the input size.1 company
Patterns
MathCombinatoricsCounting
Data structures
ArrayHash Table
Companies
Mitsogo

Prompt

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

Approaches

2 approaches with complexity analysis and trade-offs.

A straightforward but inefficient approach is to iterate through every cell in the grid. For each cell containing a 1, we consider it as the potential vertex of the right angle of a triangle. Then, we count how many other 1s exist in the same row and how many exist in the same column. The product of these two counts gives the number of right triangles that can be formed with the current cell as the corner.

Algorithm

  • Initialize a counter total_triangles to 0.
  • Get the dimensions of the grid, m rows and n columns.
  • Iterate through each cell (i, j) from (0, 0) to (m-1, n-1).
  • If grid[i][j] is 0, skip to the next cell.
  • If grid[i][j] is 1, treat it as the corner of a potential right triangle.
    • Initialize row_ones = 0 and col_ones = 0.
    • Iterate through row i (from column 0 to n-1). For each cell (i, k) where k != j, if grid[i][k] is 1, increment row_ones.
    • Iterate through column j (from row 0 to m-1). For each cell (l, j) where l != i, if grid[l][j] is 1, increment col_ones.
    • Add the product row_ones * col_ones to total_triangles.
  • After iterating through all cells, return total_triangles.

Walkthrough

The algorithm iterates through each cell (i, j) of the m x n grid. If grid[i][j] is 1, it initiates two more loops. The first inner loop scans the entire row i to count other cells (i, k) (where k != j) that contain a 1. The second inner loop scans the entire column j to count other cells (l, j) (where l != i) that contain a 1. Let these counts be row_ones and col_ones respectively. The number of right triangles with (i, j) as the corner is row_ones * col_ones. This product is added to a running total. This process is repeated for every cell in the grid.

class Solution {    public long numberOfRightTriangles(int[][] grid) {        int m = grid.length;        int n = grid[0].length;        long count = 0;         for (int i = 0; i < m; i++) {            for (int j = 0; j < n; j++) {                if (grid[i][j] == 1) {                    long rowOnes = 0;                    for (int k = 0; k < n; k++) {                        if (k != j && grid[i][k] == 1) {                            rowOnes++;                        }                    }                     long colOnes = 0;                    for (int l = 0; l < m; l++) {                        if (l != i && grid[l][j] == 1) {                            colOnes++;                        }                    }                     count += rowOnes * colOnes;                }            }        }        return count;    }}

Complexity

Time

O(m * n * (m + n)), where `m` is the number of rows and `n` is the number of columns. For each of the `m * n` cells, we traverse its row (n elements) and its column (m elements). This results in a cubic time complexity in the larger dimension, which is too slow for the given constraints.

Space

O(1), as we only use a few variables to store counts, not dependent on the input size.

Trade-offs

Pros

  • Simple to conceptualize and implement.

  • Requires no additional space.

Cons

  • Highly inefficient due to redundant calculations.

  • Will likely result in a 'Time Limit Exceeded' error for large grids.

Solutions

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;  }}

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem