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.

#3128

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

直角三角形

给你一个二维 boolean 矩阵 grid 。如果 grid 的 3 个元素的集合中，一个元素与另一个元素在同一行，并且与第三个元素在同一列，则该集合是一个直角三角形。3 个元素不必彼此相邻。请你返回使用 grid 中的 3 个元素可以构建的直角三角形数目，且满足 3 个元…

数组哈希表数学组合数学计数

题目描述

给你一个二维 boolean 矩阵 grid 。

如果 grid 的 3 个元素的集合中，一个元素与另一个元素在 同一行，并且与第三个元素在 同一列，则该集合是一个 直角三角形。3 个元素不必彼此相邻。

请你返回使用 grid 中的 3 个元素可以构建的 直角三角形 数目，且满足 3 个元素值都为 1 。

示例 1：

0	1	0
0	1	1
0	1	0

0	1	0
0	1	1
0	1	0

输入：grid = [[0,1,0],[0,1,1],[0,1,0]]

输出：2

解释：

有 2 个值为 1 的直角三角形。注意蓝色的那个没有组成直角三角形，因为 3 个元素在同一列。

示例 2：

1	0	0
0	1	1
1	0	0

输入：grid = [[1,0,0,0],[0,1,0,1],[1,0,0,0]]

输出：0

解释：

没有值为 1 的直角三角形。注意蓝色的那个没有组成直角三角形。

示例 3：

1	0	1
1	0	0
1	0	0

1	0	1
1	0	0
1	0	0

输入：grid = [[1,0,1],[1,0,0],[1,0,0]]

输出：2

解释：

有两个值为 1 的直角三角形。

提示：

1 <= grid.length <= 1000
1 <= grid[i].length <= 1000
0 <= grid[i][j] <= 1

lightbulb

解题思路

方法一：计数 + 枚举

我们可以先统计每一行和每一列的 $1$ 的个数，记录在数组 $rows$ 和 $cols$ 中。

然后我们枚举每一个 $1$ ，假设当前 $1$ 在第 $i$ 行第 $j$ 列，那么以当前 $1$ 为直角三角形的直角点，另外两个直角点分别在第 $i$ 行和第 $j$ 列，那么直角三角形的个数就是 $(rows[i] - 1) \times (cols[j] - 1)$ ，累加到答案中即可。

时间复杂度 $O(m \times n)$ ，空间复杂度 $O(m + n)$ 。其中 $m$ 和 $n$ 分别是矩阵的行数和列数。

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

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

speed

复杂度分析

指标	值
时间	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.
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Ask how you would track 1s efficiently in rows and columns.
question_mark
Check if candidate triangles are double-counted and how to prevent it.
question_mark
Discuss time-space trade-offs between scanning every triple vs hash-based lookup.

warning

常见陷阱

外企场景

error
Counting triples that are not right triangles because all three are in the same row or column.
error
Overcounting triangles when the same 1 is used multiple times without adjusting for overlaps.
error
Failing to precompute row and column 1s, leading to O(n^3) brute-force checks.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Right triangles in a grid where cells can have weights instead of boolean values.
arrow_right_alt
Counting right triangles when diagonals or L-shaped configurations are also considered.
arrow_right_alt
Extending to 3D grids to count axis-aligned right triangles in a voxel space.

help

常见问题

外企场景

继续练习

#3312 查询排序后的最大公约数 #3153 所有数对中数位差之和 #3044 出现频率最高的质数