Right Triangles - Solution & Explanation
Problem Statement
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
Approach Overview
Problem 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 1: Row-Column Counting Approach
This approach involves counting the number of 1s in each row and column of the grid. For each element at position (i, j), if grid[i][j] is 1, then the number of right triangles that can be made with (i, j) as the right-angle corner is determined by using the formula (row_count[i] - 1) * (col_count[j] - 1). This formula works by fixing one row and one column and removing the current corner element from each count.
The Python solution begins by initializing two lists, row_count and col_count, to store the count of 1s in each row and column, respectively. After populating these lists, it iterates over each grid element to calculate the potential triangles with that element as the hypotenuse corner using the formula (row_count[i] - 1) * (col_count[j] - 1). The solution finally returns the accumulated triangle count.
Code
Python
JavaScript
Complexity
Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. Space Complexity: O(n + m) for storing row and column counts.
Approach 2: Efficient Single Pass with Pre-Counting
Rather than counting 1s separately, this approach involves calculating the right triangles during a single pass through all grid cells. It pre-computes counts for easier access, leveraging cumulative techniques to reduce repetitive operations.
This C++ solution uses vectors to manage 1s counts for rows and columns. It streamlines the process by calculating potential triangles directly after initializing and populating these counts in a single traversal of the grid.
Complexity
Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. Space Complexity: O(n + m) for storing row and column counts.
Approach 3: Counting + Enumeration
First, we can count the number of 1s 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.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Row-Column Counting Approach | Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. Space Complexity: O(n + m) for storing row and column counts. |
| Efficient Single Pass with Pre-Counting | Time Complexity: O(n * m), where n is the number of rows and m is the number of columns. Space Complexity: O(n + m) for storing row and column counts. |
| Counting + Enumeration | — |
Detailed Complexity Analysis
| 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 |
Video Solution
3128. Right Triangles | Math | Array | Biweekly Contest 129 • Aryan Mittal • 1,830 views views
Watch 5 more video solutions →Frequently Asked Questions
Is Right Triangles easy or hard?
Right Triangles Python/Java solution
How to solve Right Triangles in O(n)?
What is the best approach for Right Triangles?
Is Right Triangles asked at Google/Amazon/Meta?
What data structure is used in Right Triangles?
What is the time complexity of Right Triangles?
Ready to solve this problem?
Practice Right Triangles with our built-in code editor and test cases.
Practice on FleetCodeTable of Contents
Practice this problem
Open in Editor