Start by scanning each row and column to record positions of 1s, using hash maps for quick lookups. For every cell with value 1, check pairs in its row and column to count valid right triangles efficiently. This method avoids redundant checks and ensures accurate triangle counting in large grids.
Problem Statement
You are given a 2D boolean matrix grid. A right triangle is formed by three 1-valued cells such that one cell shares a row with another and shares a column with the third. The cells do not need to be adjacent.
Return the total number of right triangles that can be formed from the 1-valued elements in grid. The matrix can be large, so efficiency is crucial, making array scanning plus hash lookup the recommended approach.
Examples
Example 1
Input: grid = [[0,1,0],[0,1,1],[0,1,0]]
Output: 2
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
Input: grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]
Output: 0
There are no right triangles with elements of the value 1. Notice that the blue ones do not form a right triangle.
Example 3
Input: grid = [[1,0,1],[1,0,0],[1,0,0]]
Output: 2
There are two right triangles with elements of the value 1.
Constraints
- 1 <= grid.length <= 1000
- 1 <= grid[i].length <= 1000
- 0 <= grid[i][j] <= 1
Solution Approach
Row and Column Mapping
Use hash maps to record positions of 1s for each row and column. This allows quick identification of candidate cells that can form right triangles with any given 1.
Iterate Through Ones
For each cell with value 1, consider pairs in its row and column to check potential right triangle formations. Multiply row count by column count minus overlapping cells to avoid double counting.
Aggregate Triangle Count
Sum all valid triangles found for each 1-valued cell. This approach leverages the precomputed maps to maintain linear scanning without unnecessary nested loops over all triples.
Complexity Analysis
| Metric | Value |
|---|---|
| Time | Depends on the final approach |
| Space | Depends on the final approach |
Time complexity depends on the number of 1s in the grid since each is checked against row and column mappings, making it O(R*C) in worst case. Space complexity is O(R + C) for the hash maps storing positions.
What Interviewers Usually Probe
- Ask how you would track 1s efficiently in rows and columns.
- Check if candidate triangles are double-counted and how to prevent it.
- Discuss time-space trade-offs between scanning every triple vs hash-based lookup.
Common Pitfalls or Variants
Common pitfalls
- Counting triples that are not right triangles because all three are in the same row or column.
- Overcounting triangles when the same 1 is used multiple times without adjusting for overlaps.
- Failing to precompute row and column 1s, leading to O(n^3) brute-force checks.
Follow-up variants
- Right triangles in a grid where cells can have weights instead of boolean values.
- Counting right triangles when diagonals or L-shaped configurations are also considered.
- Extending to 3D grids to count axis-aligned right triangles in a voxel space.
How GhostInterview Helps
- Highlights which 1s can pair with others efficiently using hash lookup to reduce unnecessary iterations.
- Automatically flags overcounting by tracking row and column associations for each 1.
- Provides a systematic count aggregation to quickly produce the correct number of right triangles.
Topic Pages
Related GhostInterview Pages
- LeetCode Interview Copilot - Use GhostInterview as a live solver when you want direct help with LeetCode-style coding questions.
- Coding Interview Assistant - See how GhostInterview supports array, string, linked list, graph, and tree interview workflows.
- How GhostInterview Works - Review the screenshot, reasoning, and answer flow before using the solver in a live interview.
FAQ
What exactly defines a right triangle in this grid problem?
A right triangle is formed by three 1-valued cells where one shares a row with another and shares a column with the third.
How can I avoid overcounting triangles in the same row or column?
Precompute positions of 1s in rows and columns using hash maps and calculate products of counts minus overlaps.
Does this approach work efficiently for large grids?
Yes, using array scanning plus hash lookup reduces the need to check every triple, keeping performance manageable for grids up to 1000x1000.
Can triangles overlap in cells?
Yes, a single 1 can participate in multiple triangles, but counting uses row and column maps to prevent double-counting the same configuration.
Why is array scanning plus hash lookup the recommended pattern here?
It efficiently identifies candidate 1s in rows and columns for right triangles, avoiding the O(n^3) brute-force approach.
Need direct help with Right Triangles instead of spending more time grinding it?
Download GhostInterview when you want a LeetCode solver, not another long practice loop. Capture Right Triangles from a screenshot, get the answer path and complexity, and use supported stealth workflows that stay outside captured layers.
Capture the prompt fast instead of rewriting the problem by hand.
Get the solution path, trade-offs, and complexity summary in one pass.
Stay outside captured layers on supported screen-share workflows.
Stay in the same pattern family
Solve the Sorted GCD Pair Queries problem by efficiently counting and locating GCDs of all array pairs using hash mapping.
Open problem page#3153 Sum of Digit Differences of All PairsSum of Digit Differences of All Pairs is a problem that involves counting digit differences in pairs from an array of integers.
Open problem page#3044 Most Frequent PrimeFind the most frequent prime over 10 from numbers generated by scanning a 2D matrix in all straight directions efficiently.
Open problem page