Welcome to Subscribe On Youtube
3128. Right Triangles
Description
You are given a 2D boolean matrix grid.
Return an integer that is the number of right triangles that can be made with the 3 elements of grid such that all of them have a value of 1.
Note:
- A collection of 3 elements of
gridis 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 do not have to be next to each other.
Example 1:
| 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.
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.
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.
Constraints:
1 <= grid.length <= 10001 <= grid[i].length <= 10000 <= 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.
-
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 ans -
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 } -
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; }