You are given a 2D integer array points, where points[i] = [xi, yi] represents the coordinates of the ith point on the Cartesian plane.
A horizontal trapezoid is a convex quadrilateral with at least one pair of horizontal sides (i.e. parallel to the x-axis). Two lines are parallel if and only if they have the same slope.
Return the number of unique horizontal trapezoids that can be formed by choosing any four distinct points from points.
Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: points = [[1,0],[2,0],[3,0],[2,2],[3,2]]
Output: 3
Explanation:
There are three distinct ways to pick four points that form a horizontal trapezoid:
[1,0], [2,0], [3,2], and [2,2].[2,0], [3,0], [3,2], and [2,2].[1,0], [3,0], [3,2], and [2,2].Example 2:
Input: points = [[0,0],[1,0],[0,1],[2,1]]
Output: 1
Explanation:
There is only one horizontal trapezoid that can be formed.
Constraints:
4 <= points.length <= 105–108 <= xi, yi <= 108Problem Overview: You are given points on a 2D plane. A trapezoid requires at least one pair of parallel sides. The key observation is that any pair of points sharing the same y-coordinate forms a horizontal segment, and two horizontal segments on different y levels can act as the parallel sides of a trapezoid.
Approach 1: Enumeration with Y-Level Grouping (O(n + k2) time, O(n) space)
Group points by their y-coordinate using a hash map. If a level has m points, you can form C(m,2) horizontal segments on that line. Each segment represents a possible base of a trapezoid. Store the number of segments for every y-level.
Next, enumerate every pair of distinct y-levels. If level i has a horizontal segments and level j has b, then you can form a * b trapezoids using one segment from each level as the parallel sides. The non-parallel sides are implicitly defined by connecting the endpoints. Summing this product across all pairs of levels gives the total trapezoid count.
The hash table groups points efficiently, while simple array enumeration handles combinations of levels. The geometric insight is that parallel horizontal segments guarantee a trapezoid regardless of the remaining edges. This reduces a geometric counting problem to a combination counting problem using math and hashing.
Space complexity is O(n) to store the frequency of points per y-level. Time complexity is dominated by counting segments and iterating over pairs of distinct levels. If there are k unique y-coordinates, the pair enumeration costs O(k^2).
Recommended for interviews: The hash map + enumeration approach is the expected solution. It shows you can convert a geometry problem into counting combinations. A brute force check of all quadruples of points would be O(n^4) and only demonstrates baseline understanding, while grouping by y-coordinate and counting segment pairs shows stronger algorithmic reasoning.
According to the problem description, horizontal edges have the same y coordinate. Therefore, we can group points by their y coordinates and count the number of points for each y coordinate.
We use a hash table cnt to store the number of points for each y coordinate. For each y coordinate y_i, assuming the number of corresponding points is v, the number of ways to select two points from these points as a horizontal edge is \binom{v}{2} = \frac{v(v-1)}{2}, denoted as t.
We use a variable s to record the sum of the number of horizontal edges for all previous y coordinates. Then, we can multiply the number of horizontal edges t for the current y coordinate by the sum s of the number of horizontal edges for all previous y coordinates to get the number of trapezoids with the current y coordinate as one pair of horizontal edges, and add it to the answer. Finally, we add the number of horizontal edges t for the current y coordinate to s for subsequent calculations.
Note that since the answer may be very large, we need to take the modulo 10^9 + 7.
The time complexity is O(n) and the space complexity is O(n), where n is the number of points.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Quadruple Enumeration | O(n^4) | O(1) | Conceptual baseline; useful for verifying small inputs |
| Enumerate All Segments and Check Parallelism | O(n^2) | O(n^2) | General geometry problems where slopes must be compared |
| Hash Map by Y-Level + Segment Pair Enumeration | O(n + k^2) | O(n) | Optimal for horizontal parallel sides; typical interview solution |
Count Number of Trapezoids I | Simplest Explanation | Detailed | Leetcode 3623 | codestorywithMIK • codestorywithMIK • 7,405 views views
Watch 9 more video solutions →Practice Count Number of Trapezoids I with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor