You are given a 2D integer array points where points[i] = [xi, yi] represents the coordinates of the ith point on the Cartesian plane.
Return the number of unique trapezoids that can be formed by choosing any four distinct points from points.
A trapezoid is a convex quadrilateral with at least one pair of parallel sides. Two lines are parallel if and only if they have the same slope.
Example 1:
Input: points = [[-3,2],[3,0],[2,3],[3,2],[2,-3]]
Output: 2
Explanation:
There are two distinct ways to pick four points that form a trapezoid:
[-3,2], [2,3], [3,2], [2,-3] form one trapezoid.[2,3], [3,2], [3,0], [2,-3] form another trapezoid.Example 2:
Input: points = [[0,0],[1,0],[0,1],[2,1]]
Output: 1
Explanation:
There is only one trapezoid which can be formed.
Constraints:
4 <= points.length <= 500–1000 <= xi, yi <= 1000Problem Overview: You are given points on a 2D plane and need to count how many unique trapezoids can be formed. A trapezoid is a quadrilateral with at least one pair of parallel sides, so the task reduces to identifying pairs of parallel segments that can act as the bases.
Approach 1: Hash Table + Enumeration (O(n2) time, O(n2) space)
Enumerate every pair of points (i, j) and treat the segment between them as a potential base of a trapezoid. Compute its slope using basic math and normalize it (e.g., reduce the fraction of dy/dx) so parallel segments share the same representation. Use a hash table to group segments by slope.
Inside each slope group, segments lie on many different lines. Two segments can form the parallel sides of a trapezoid only if they belong to different lines (different intercepts) and do not share endpoints. Store additional identifiers such as line intercept or midpoint to distinguish segments. Count how many pairs of segments with the same slope lie on different lines. Each valid pair contributes trapezoids when their endpoints form four distinct vertices.
This converts a geometric constraint into a counting problem. Instead of checking every quadruple of points, you first enumerate all segments in O(n^2), group them with hashing, and then count combinations within each slope bucket. Geometry calculations are simple integer operations, which keeps the approach efficient even for large inputs.
The key insight: trapezoids exist when two segments are parallel but not collinear. Grouping by slope avoids repeated comparisons and lets you count candidates quickly using frequency counts and combinations. This pattern—enumerate pairs, normalize a geometric property, and aggregate with hashing—is common in geometry counting problems.
Recommended for interviews: The hash table + enumeration approach is what interviewers expect. A brute force over every quadruple of points is easy to reason about but runs in O(n^4), which is impractical. Enumerating segments and grouping by slope demonstrates strong problem decomposition and efficient use of hashing.
We can combine all points pairwise, calculate the slope and intercept of the line corresponding to each pair of points, record them using a hash table, and calculate the sum of the number of pairs formed by lines with the same slope but different intercepts. Note that for parallelograms, we will count them twice in the above calculation, so we need to subtract them.
The diagonals of a parallelogram share the same midpoint. Therefore, we also combine all points pairwise, calculate the midpoint coordinates and slope of each pair of points, record them using a hash table, and calculate the sum of the number of pairs formed by point pairs with the same slope and the same midpoint coordinates.
Specifically, we use two hash tables cnt1 and cnt2 to record the following information:
cnt1 records the number of occurrences of slope k and intercept b, with the key being the slope k and the value being another hash table that records the number of occurrences of intercept b;cnt2 records the number of occurrences of the midpoint coordinates and slope k of point pairs, with the key being the midpoint coordinates p of the point pair and the value being another hash table that records the number of occurrences of slope k.For a point pair (x_1, y_1) and (x_2, y_2), we denote dx = x_2 - x_1 and dy = y_2 - y_1. If dx = 0, it means the two points are on the same vertical line, and we denote the slope k = +infty and the intercept b = x_1; otherwise, the slope k = \frac{dy}{dx} and the intercept b = \frac{y_1 cdot dx - x_1 cdot dy}{dx}. The midpoint coordinates p of the point pair can be expressed as p = (x_1 + x_2 + 2000) cdot 4000 + (y_1 + y_2 + 2000), where the offset is added to avoid negative numbers.
Next, we iterate through all point pairs, calculate the corresponding slope k, intercept b, and midpoint coordinates p, and update the hash tables cnt1 and cnt2.
Then, we iterate through the hash table cnt1. For each slope k, we calculate the sum of all pairwise combinations of the occurrence counts of intercept b and add it to the answer. Finally, we iterate through the hash table cnt2. For each midpoint coordinate p, we calculate the sum of all pairwise combinations of the occurrence counts of slope k and subtract it from the answer.
The time complexity is O(n^2) and the space complexity is O(n^2), where n is the number of points.
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force (Check All Quadruples) | O(n^4) | O(1) | Only for understanding the geometry or very small input sizes |
| Hash Table + Segment Enumeration | O(n^2) | O(n^2) | General case; groups parallel segments by slope and counts valid pairs efficiently |
| Slope Grouping with Line Separation | O(n^2) | O(n^2) | Preferred optimized implementation that avoids counting collinear segments |
Count Number of Trapezoids II | Detailed in Simple Words | Leetcode 3625 | codestorywithMIK • codestorywithMIK • 6,094 views views
Watch 9 more video solutions →Practice Count Number of Trapezoids II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor