3128. Right Triangles
Asked by 2 companies
Topics
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
Hints
Hint 1
grid[x][y] is 1, it can form a right triangle with an element of grid with value 1 in the same row and an element of grid with value 1 in the same column.Hint 2
Hint 3
x, y with grid[x][y] = 1 if there are row[x] 1s in the row x and col[y] 1s in column y, the answer should be added by (row[x] - 1) * (col[y] - 1).