How do I count the number of horizontal trapezoids efficiently?

Efficiently count trapezoids by scanning through the points and grouping them by their y-coordinate using a hash table. Then, calculate the possible trapezoids from those groups.

What is the primary pattern in this problem?

The primary pattern is array scanning plus hash lookup, which helps categorize points by their y-coordinate to identify potential trapezoids.

Can the approach handle large input sizes?

Yes, the approach is designed to handle inputs up to 10^5 points efficiently by utilizing hash tables for fast lookups.

What role does the y-coordinate play in forming a trapezoid?

The y-coordinate determines which points can form the horizontal sides of the trapezoid, as these sides must be parallel to the x-axis.

How do I optimize the solution for this problem?

Optimize by categorizing points by y-coordinate using a hash table, which enables fast lookups and efficient counting of potential trapezoids.

#3623

Medium

auto_awesome数组·哈希·扫描

LeetCode 题解工作台

统计梯形的数目 I

给你一个二维整数数组 points ，其中 points[i] = [x i , y i ] 表示第 i 个点在笛卡尔平面上的坐标。水平梯形是一种凸四边形，具有至少一对水平边（即平行于 x 轴的边）。两条直线平行当且仅当它们的斜率相同。返回可以从 points 中任意选择四个不同点组成的 …

数组哈希表数学几何

题目描述

给你一个二维整数数组 points，其中 points[i] = [x_i, y_i] 表示第 i 个点在笛卡尔平面上的坐标。

水平梯形 是一种凸四边形，具有 至少一对 水平边（即平行于 x 轴的边）。两条直线平行当且仅当它们的斜率相同。

返回可以从 points 中任意选择四个不同点组成的 水平梯形 数量。

由于答案可能非常大，请返回结果对 10⁹ + 7 取余数后的值。

示例 1：

输入： points = [[1,0],[2,0],[3,0],[2,2],[3,2]]

输出： 3

解释：

有三种不同方式选择四个点组成一个水平梯形：

使用点 [1,0]、[2,0]、[3,2] 和 [2,2]。
使用点 [2,0]、[3,0]、[3,2] 和 [2,2]。
使用点 [1,0]、[3,0]、[3,2] 和 [2,2]。

示例 2：

输入： points = [[0,0],[1,0],[0,1],[2,1]]

输出： 1

解释：

只有一种方式可以组成一个水平梯形。

提示：

4 <= points.length <= 10⁵
–10⁸ <= x_i, y_i <= 10⁸
所有点两两不同。

lightbulb

解题思路

方法一：枚举

根据题目描述，水平边满足 $y$ 坐标相同，因此我们可以根据 $y$ 坐标将点进行分组，统计每个 $y$ 坐标对应的点的数量。

我们用一个哈希表 $\textit{cnt}$ 来存储每个 $y$ 坐标对应的点的数量。对于每个 $y$ 坐标 $y_i$ ，假设对应的点的数量为 $v$ ，那么从这些点中选择两点作为水平边的方式有 $\binom{v}{2} = \frac{v(v-1)}{2}$ 种，记为 $t$ 。

我们用一个变量 $s$ 来记录之前所有 $y$ 坐标对应的水平边的数量之和。那么，我们可以将当前 $y$ 坐标对应的水平边的数量 $t$ 与之前所有 $y$ 坐标对应的水平边的数量之和 $s$ 相乘，得到以当前 $y$ 坐标为一对水平边的梯形的数量，并将其累加到答案中。最后，我们将当前 $y$ 坐标对应的水平边的数量 $t$ 累加到 $s$ 中，以便后续计算。

注意，由于答案可能非常大，我们需要对 $10^9 + 7$ 取余数。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 是点的数量。

1

2

3

4

5

6

7

8

9

10

11

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        mod = 10**9 + 7
        cnt = Counter(p[1] for p in points)
        ans = s = 0
        for v in cnt.values():
            t = v * (v - 1) // 2
            ans = (ans + s * t) % mod
            s += t
        return ans

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Candidate demonstrates understanding of geometric properties like parallel lines.
question_mark
Candidate efficiently uses hash tables to track and group points.
question_mark
Candidate is able to optimize their approach to handle the input size constraint.

warning

常见陷阱

外企场景

error
Misunderstanding the concept of parallel lines, leading to incorrect trapezoid formation.
error
Failure to account for all distinct point combinations.
error
Not optimizing the approach to handle larger inputs within time limits.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Implementing the solution in a higher-dimensional space.
arrow_right_alt
Extending the solution to count trapezoids with vertical sides as well.
arrow_right_alt
Exploring alternative approaches like sorting or dynamic programming.

help

常见问题

外企场景

继续练习

#3625 统计梯形的数目 II #3588 找到最大三角形面积 #3591 检查元素频次是否为质数