#3128

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Right Triangles

Count all possible right triangles in a 2D boolean grid using array scanning and hash lookup for efficiency.

array hash table math combinatorics counting

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.

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.

terminal

Solution

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$.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

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

Continue Practicing

#3312 sorted gcd pair queries #3153 sum of digit differences of all pairs #3044 most frequent prime