Watch 6 video solutions for Right Triangles, a medium level problem involving Array, Hash Table, Math. This walkthrough by Aryan Mittal has 1,802 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 1Problem Overview: You get a binary m x n grid. A right triangle is valid when its right angle sits on a cell containing 1, with one leg extending along the row and the other along the column. The task is to count how many such triangles exist in the grid.
Approach 1: Row-Column Counting Approach (O(m*n) time, O(m+n) space)
The key observation: if a cell (i, j) contains 1, it can serve as the right-angle corner of multiple triangles. Any other 1 in the same row forms the horizontal leg, and any other 1 in the same column forms the vertical leg. If a row contains r ones and a column contains c ones, the number of triangles with the right angle at (i, j) equals (r - 1) * (c - 1). First iterate through the grid and count how many 1s appear in each row and column. Then iterate again and for every 1 accumulate (rowCount[i] - 1) * (colCount[j] - 1). This uses simple frequency arrays and relies on basic array traversal and counting techniques.
Approach 2: Efficient Single Pass with Pre-Counting (O(m*n) time, O(m+n) space)
You can streamline the counting by precomputing row and column totals once, then computing triangle contributions during a single grid traversal. After building rowCount and colCount, scan the grid and directly apply the formula whenever grid[i][j] == 1. Each cell contributes independently, so the algorithm avoids nested searches for row or column partners. The runtime stays linear in the number of cells, and memory usage remains proportional to the number of rows and columns. Conceptually this is a combinatorics problem: choose one horizontal partner and one vertical partner from the available counts.
Recommended for interviews: The row–column counting strategy is what interviewers expect. A brute-force idea would try every triplet of cells and check if they form a right triangle, which quickly becomes cubic time. Showing that idea briefly demonstrates understanding of the geometry, but switching to row and column frequency counting shows algorithmic maturity. The optimal O(m*n) approach uses simple data structures, scales well to large grids, and clearly communicates the combinatorial insight behind the problem.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplet Check | O((m*n)^3) | O(1) | Conceptual baseline to understand triangle formation |
| Row-Column Counting | O(m*n) | O(m+n) | General optimal approach for counting triangles in a binary grid |
| Single Pass with Pre-Counting | O(m*n) | O(m+n) | When row and column frequencies are precomputed and reused |