Right Triangles
MedPrompt
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 <= 10001 <= grid[i].length <= 10000 <= 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_trianglesto 0. - Get the dimensions of the grid,
mrows andncolumns. - 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 = 0andcol_ones = 0. - Iterate through row
i(from column 0 ton-1). For each cell(i, k)wherek != j, ifgrid[i][k]is 1, incrementrow_ones. - Iterate through column
j(from row 0 tom-1). For each cell(l, j)wherel != i, ifgrid[l][j]is 1, incrementcol_ones. - Add the product
row_ones * col_onestototal_triangles.
- Initialize
- 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.
This approach optimizes the brute-force method by eliminating redundant computations. The key observation is that for each cell (i, j), the brute-force method re-calculates the number of 1s in row i and column j. We can significantly improve performance by pre-calculating the total number of 1s in each row and each column in a single pass.
Algorithm
- Get the dimensions of the grid,
mrows andncolumns. - Create an integer array
row_countsof sizemandcol_countsof sizen, both initialized to zero. - Iterate through the grid from
(0, 0)to(m-1, n-1). Ifgrid[i][j]is 1, incrementrow_counts[i]andcol_counts[j]. - Initialize a long integer
total_trianglesto 0. - Iterate through the grid again from
(0, 0)to(m-1, n-1). - If
grid[i][j]is 1:- Calculate the number of other
1s in the same row:other_row_ones = row_counts[i] - 1. - Calculate the number of other
1s in the same column:other_col_ones = col_counts[j] - 1. - Add the product
other_row_ones * other_col_onestototal_triangles.
- Calculate the number of other
- Return
total_triangles.
Walkthrough
The algorithm consists of two main phases.
First, the pre-computation phase: We create two arrays, row_counts of size m and col_counts of size n, initialized to zeros. We then iterate through the entire grid once. For each cell (i, j) that contains a 1, we increment row_counts[i] and col_counts[j]. After this pass, row_counts[i] will hold the total number of 1s in row i, and col_counts[j] will hold the total for column j.
Second, the counting phase: We iterate through the grid again. For each cell (i, j) where grid[i][j] is 1, we can find the number of other 1s in its row and column in constant time using our pre-computed arrays. The number of other 1s in row i is row_counts[i] - 1, and in column j is col_counts[j] - 1. The number of right triangles with (i, j) as the corner is the product of these two values. We sum these products for all 1s in the grid to get the final answer. A long data type should be used for the total count to prevent overflow.
class Solution { public long numberOfRightTriangles(int[][] grid) { int m = grid.length; int n = grid[0].length; int[] rowCounts = new int[m]; int[] colCounts = new int[n]; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { rowCounts[i]++; colCounts[j]++; } } } long totalTriangles = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 1) { long otherRowOnes = rowCounts[i] - 1; long otherColOnes = colCounts[j] - 1; if (otherRowOnes > 0 && otherColOnes > 0) { totalTriangles += otherRowOnes * otherColOnes; } } } } return totalTriangles; }}Complexity
Time
O(m * n), where `m` is the number of rows and `n` is the number of columns. The algorithm involves two separate passes over the grid, each taking `O(m * n)` time. This is linear with respect to the number of cells in the grid.
Space
O(m + n). We use two arrays to store the counts of `1`s for each row and column.
Trade-offs
Pros
Optimal time complexity, making it very fast for large grids.
The logic is still relatively simple to follow.
Cons
Requires extra space for the count arrays, which could be a concern for extremely large (but sparse) grids, though not for the given constraints.
Solutions
Solution
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; }}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; }};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 ansVideo 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.