3623. Count Number of Trapezoids I

MediumGeometryArrayHash TableMath

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a 2D integer array points, where points[i] = [xᵢ, yᵢ] represents the coordinates of the i-th point on the Cartesian plane.

A horizontal trapezoid is a convex quadrilateral that has at least one pair of horizontal sides (i.e. sides that are parallel to the x-axis). Two lines are considered parallel if and only if they share the same slope.

Your task is to count the number of unique horizontal trapezoids that can be formed by choosing any four distinct points from points.

The key observation here is that a horizontal side is simply a segment connecting two points that have the same y coordinate. To build a horizontal trapezoid, you need to pick two such horizontal segments lying on different y levels, which together provide the four corner points of the quadrilateral.

For example:

A pair of points like [1, 3] and [5, 3] forms one horizontal side because they share the same y value of 3.
A pair like [2, 7] and [6, 7] forms another horizontal side at the y level of 7.
Combining these two horizontal sides gives you a valid horizontal trapezoid.

Since the final count can be extremely large, you should return the answer modulo 10⁹ + 7.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Hash Table / Counting?

This problem maps to Hash Table / Counting through a short path in the full flowchart.

The problem groups points by y-coordinate, counts segments per level using combinations, then pairs segments across different levels for the trapezoid count.

Open in Flowchart

Intuition

The first thing to notice is what makes a trapezoid "horizontal". Since a horizontal side must be parallel to the x-axis, the two endpoints of such a side must share the same y coordinate. This immediately tells us that the x coordinates don't really matter for counting — what matters is how many points sit on each horizontal level (each y value).

So a natural idea is to group the points by their y coordinate. If a certain y level has v points on it, then any two of those points can form a horizontal segment. The number of such segments at that level is the number of ways to choose 2 points out of v, which is C(v, 2) = v * (v - 1) / 2. Let's call this value t for that level.

Now, a horizontal trapezoid needs exactly two horizontal sides, and these two sides must lie at different y levels (otherwise the four points would be collinear and couldn't form a quadrilateral). So the problem reduces to: pick one horizontal segment from one level, and another horizontal segment from a different level. Every such pairing produces a unique horizontal trapezoid.

This means the answer is the sum, over every pair of distinct y levels, of the product of their segment counts. If level i has tᵢ segments and level j has tⱼ segments, that pair contributes tᵢ * tⱼ trapezoids.

To compute this sum of products efficiently without checking every pair, we process the levels one at a time and keep a running total s of the segment counts seen so far. When we reach a new level with t segments, every previously accumulated segment can be paired with the current ones, contributing s * t to the answer. After adding that, we update s += t so the next level can pair against everything before it. This sweeping technique turns an O(n²) pairwise calculation into a single linear pass.

Finally, because the result can grow very large, we take everything modulo 10⁹ + 7 as we go.

Pattern Learn more about Math patterns.

Solution Approach

We use the Enumeration technique together with a hash table (Counter) to group points and accumulate the answer in a single pass.

Step 1: Group points by their y coordinate.

Since horizontal sides require two points sharing the same y value, we only care about how many points lie on each horizontal level. We build a hash table cnt where the key is a y coordinate and the value is the number of points on that level:

cnt = Counter(p[1] for p in points)

Step 2: Count horizontal segments per level.

For a level with v points, the number of ways to choose 2 points to form a horizontal segment is the combination C(v, 2):

t = v * (v - 1) // 2

This t is the number of horizontal sides available at the current y level.

Step 3: Combine segments across different levels with a running sum.

A horizontal trapezoid is formed by pairing one segment from the current level with one segment from any previous level. We maintain a variable s that holds the total number of segments seen across all earlier levels. When we process the current level with t segments, the number of new trapezoids it forms is s * t, since each earlier segment can pair with each current segment:

ans = (ans + s * t) % mod
s += t

After adding the contribution, we update s += t so that future levels can pair against the current one too. This running-sum trick avoids the O(n²) cost of checking every pair of levels explicitly, reducing it to a single linear sweep.

Step 4: Apply the modulo.

Because the answer can be huge, we take the result modulo 10⁹ + 7 at each accumulation step to prevent overflow and meet the problem's requirement:

mod = 10**9 + 7

Complexity Analysis:

Time complexity: O(n), where n is the number of points. Building the Counter takes O(n), and iterating over its values takes at most O(n).
Space complexity: O(n), for storing the counts of points grouped by their y coordinate in the hash table.

Example Walkthrough

Let's trace through the solution approach with a small concrete example.

Input:

points = [[1, 3], [5, 3], [8, 3], [2, 7], [6, 7], [4, 1]]

Step 1: Group points by their y coordinate.

We scan every point and tally how many sit on each horizontal level (y value):

`y` level	points on that level	count `v`
`3`	`[1,3]`, `[5,3]`, `[8,3]`	`3`
`7`	`[2,7]`, `[6,7]`	`2`
`1`	`[4,1]`	`1`

So our Counter becomes cnt = {3: 3, 7: 2, 1: 1}.

Step 2: Count horizontal segments per level.

For each level we compute t = C(v, 2) = v * (v - 1) / 2, the number of horizontal segments it can form:

Level y = 3: t = 3 * 2 / 2 = 3 segments → the pairs (1,3)-(5,3), (1,3)-(8,3), (5,3)-(8,3).
Level y = 7: t = 2 * 1 / 2 = 1 segment → the pair (2,7)-(6,7).
Level y = 1: t = 1 * 0 / 2 = 0 segments → a single point can't form a side.

Step 3: Combine segments across levels with a running sum.

We initialize ans = 0 and s = 0, then process the levels one by one. Remember: s holds the total segments from all previously seen levels, and each new level contributes s * t trapezoids.

Processing level	`t`	Contribution `s * t`	`ans` after	`s` after (`s += t`)
`y = 3`	`3`	`0 * 3 = 0`	`0`	`0 + 3 = 3`
`y = 7`	`1`	`3 * 1 = 3`	`3`	`3 + 1 = 4`
`y = 1`	`0`	`4 * 0 = 0`	`3`	`4 + 0 = 4`

The level y = 3 adds nothing because no prior segments exist yet (s = 0). When we reach y = 7, its single segment pairs with all 3 earlier segments from level y = 3, producing 3 trapezoids. Level y = 1 contributes 0 since it has no horizontal segment.

Step 4: Apply the modulo.

Each accumulation is taken modulo 10⁹ + 7. Here the numbers are tiny, so the result is unaffected.

Result: ans = 3.

Verification: The valid trapezoids each pair the single segment at y = 7 with one of the three segments at y = 3:

(2,7)-(6,7) with (1,3)-(5,3)
(2,7)-(6,7) with (1,3)-(8,3)
(2,7)-(6,7) with (5,3)-(8,3)

This matches our computed answer of 3, confirming the running-sum sweep correctly counts every cross-level pairing in a single linear pass.

Solution Implementation

1from typing import List
2from collections import Counter
3
4
5class Solution:
6    def countTrapezoids(self, points: List[List[int]]) -> int:
7        MOD = 10**9 + 7
8
9        # Group points by their y-coordinate (horizontal levels).
10        # A horizontal line at a given y can host multiple points.
11        y_count = Counter(point[1] for point in points)
12
13        total_trapezoids = 0  # Final answer accumulator.
14        prefix_pairs = 0      # Running sum of horizontal segment counts from previous levels.
15
16        for level_size in y_count.values():
17            # Number of horizontal segments (point pairs) on this level: C(level_size, 2).
18            pairs_on_level = level_size * (level_size - 1) // 2
19
20            # Each segment on the current level combines with every segment from
21            # previous levels to form a trapezoid (two parallel horizontal sides).
22            total_trapezoids = (total_trapezoids + prefix_pairs * pairs_on_level) % MOD
23
24            # Add the current level's segments to the prefix sum for future levels.
25            prefix_pairs += pairs_on_level
26
27        return total_trapezoids
28

1class Solution {
2    public int countTrapezoids(int[][] points) {
3        // Modulo value to prevent integer overflow in the final result
4        final int MOD = (int) 1e9 + 7;
5
6        // Map to count how many points share the same y-coordinate (lie on the same horizontal line)
7        Map<Integer, Integer> yCoordinateCount = new HashMap<>();
8        for (int[] point : points) {
9            // point[1] is the y-coordinate; accumulate the count for each horizontal line
10            yCoordinateCount.merge(point[1], 1, Integer::sum);
11        }
12
13        // answer       : total number of trapezoids found so far
14        // prefixPairs  : prefix sum of horizontal segment pairs from previously processed lines
15        long answer = 0;
16        long prefixPairs = 0;
17
18        for (int pointCount : yCoordinateCount.values()) {
19            // Number of horizontal segments (pairs of points) that can be formed on the current line:
20            // C(pointCount, 2) = pointCount * (pointCount - 1) / 2
21            long currentPairs = 1L * pointCount * (pointCount - 1) / 2;
22
23            // A trapezoid requires two parallel horizontal segments from two different lines.
24            // Combine current line's segments with all segments accumulated from previous lines.
25            answer = (answer + prefixPairs * currentPairs) % MOD;
26
27            // Add the current line's segments to the running prefix sum
28            prefixPairs += currentPairs;
29        }
30
31        return (int) answer;
32    }
33}
34

1class Solution {
2public:
3    int countTrapezoids(vector<vector<int>>& points) {
4        const int kMod = 1e9 + 7;
5
6        // Count how many points share the same y-coordinate.
7        // Points on the same horizontal line can form horizontal segments.
8        unordered_map<int, int> yCount;
9        for (const auto& point : points) {
10            yCount[point[1]]++;
11        }
12
13        // A trapezoid (with two horizontal parallel sides) is formed by
14        // choosing one horizontal segment from one y-level and another
15        // horizontal segment from a different y-level.
16        //
17        // For a y-level with v points, the number of horizontal segments
18        // (pairs of points) is C(v, 2) = v * (v - 1) / 2.
19        //
20        // We iterate over each y-level, accumulating the running total of
21        // segments seen so far (segmentPrefixSum). For the current level's
22        // segment count, multiplying by all previously counted segments
23        // gives the number of valid trapezoid combinations across levels.
24        long long answer = 0;
25        long long segmentPrefixSum = 0;
26        for (const auto& [y, v] : yCount) {
27            // Number of horizontal segments at this y-level.
28            long long segments = 1LL * v * (v - 1) / 2;
29
30            // Pair each segment at this level with every segment from
31            // previously processed levels.
32            answer = (answer + segmentPrefixSum * segments) % kMod;
33
34            // Update the running total of segments.
35            segmentPrefixSum += segments;
36        }
37
38        return static_cast<int>(answer);
39    }
40};
41

1const MOD = 1_000_000_007n;
2
3/**
4 * Counts the number of horizontal trapezoids that can be formed from the given points.
5 *
6 * A horizontal trapezoid is formed by two distinct horizontal lines (rows),
7 * where each line contains at least two points. Picking any pair of points
8 * from one row and any pair from another row yields one trapezoid.
9 *
10 * @param points - An array of [x, y] coordinate pairs.
11 * @returns The total number of trapezoids modulo 1e9 + 7.
12 */
13function countTrapezoids(points: number[][]): number {
14    // Map from y-coordinate (row) to the count of points on that row.
15    const rowCount = new Map<number, number>();
16
17    // Tally how many points lie on each horizontal line.
18    for (const point of points) {
19        const y = point[1];
20        rowCount.set(y, (rowCount.get(y) ?? 0) + 1);
21    }
22
23    let answer = 0n;
24    // Running sum of the number of point-pairs from all previously processed rows.
25    let prefixPairs = 0n;
26
27    for (const count of rowCount.values()) {
28        // Number of ways to pick 2 points from the current row: C(count, 2).
29        const currentPairs = BigInt(count) * BigInt(count - 1) / 2n;
30
31        // Each pair on a previous row combines with each pair on this row
32        // to form one trapezoid.
33        answer = (answer + prefixPairs * currentPairs) % MOD;
34
35        // Accumulate the current row's pairs into the prefix total.
36        prefixPairs += currentPairs;
37    }
38
39    return Number(answer);
40}
41

Time and Space Complexity

Time Complexity: O(n)

The analysis is broken down as follows:

Building the Counter: The expression Counter(p[1] for p in points) iterates over all n points once to extract their y-coordinates and count their frequencies. This takes O(n) time.
Iterating over the counter values: The for v in cnt.values() loop iterates over the distinct y-coordinate values. In the worst case, all points have distinct y-coordinates, so there can be up to n entries in the counter. Inside the loop, each operation (computing t, updating ans, and updating s) takes O(1) time. Therefore, this loop runs in O(n) time.

Combining these steps, the overall time complexity is O(n) + O(n) = O(n), where n is the number of points.

Space Complexity: O(n)

The dominant space cost comes from the Counter object cnt, which stores the frequency of each distinct y-coordinate. In the worst case, all n points have distinct y-coordinates, requiring O(n) space to store the counts. The remaining variables (mod, ans, s, t) use only O(1) additional space. Therefore, the overall space complexity is O(n), where n is the number of points.

Pattern Learn more about how to find time and space complexity quickly.

Common Pitfalls

Pitfall 1: Applying the modulo too late (overflow in the running sum)

A frequent mistake is taking the modulo only on the final answer, while letting the prefix_pairs running sum grow unbounded:

# WRONG: prefix_pairs is never reduced, and the product can overflow
# in languages with fixed-width integers.
total_trapezoids = total_trapezoids + prefix_pairs * pairs_on_level
...
return total_trapezoids % MOD

In Python this won't produce an incorrect result because integers are arbitrary-precision, but it makes the solution non-portable and can cause genuine overflow when translated to C++/Java. The product prefix_pairs * pairs_on_level can be astronomically large.

Solution: Reduce both the accumulator and the running prefix sum modulo MOD at every step:

pairs_on_level = level_size * (level_size - 1) // 2 % MOD
total_trapezoids = (total_trapezoids + prefix_pairs * pairs_on_level) % MOD
prefix_pairs = (prefix_pairs + pairs_on_level) % MOD

This keeps every intermediate value bounded by MOD², which is safe even for 64-bit integers.

Pitfall 2: Misinterpreting "trapezoid" and double-counting

The intuitive trap is to think you must match the lengths of the two horizontal sides or worry about whether the shape is a "proper" trapezoid vs. a parallelogram/rectangle. In this problem, any two horizontal segments on two different y levels form a valid horizontal trapezoid, regardless of their lengths or horizontal offset.

A related error is pairing segments on the same level, which would not produce a quadrilateral with two distinct horizontal sides. The running-sum design avoids this because prefix_pairs only includes levels processed before the current one — a segment never pairs with another segment on its own level.

Solution: Trust the combinatorial model: count C(v, 2) segments per level, and pair across distinct levels only. Do not add a same-level term, and do not filter by side length.

Pitfall 3: Computing `C(v, 2)` incorrectly for small levels

Levels containing only one point contribute C(1, 2) = 0 segments. If you mistakenly compute combinations with a formula that doesn't handle v < 2 (for example, indexing into a precomputed factorial table without a guard), you may get errors or negative intermediate values.

Solution: The expression v * (v - 1) // 2 naturally yields 0 for v = 0 or v = 1, so it is safe. Just ensure you use integer division (//) and not float division (/), since float results break the subsequent modular arithmetic:

pairs_on_level = level_size * (level_size - 1) // 2   # correct: integer
# pairs_on_level = level_size * (level_size - 1) / 2  # WRONG: float

Pitfall 4: Grouping by the wrong coordinate

Since horizontal sides are parallel to the x-axis, points on the same horizontal line share the same y value (point[1]). A subtle bug is grouping by point[0] (the x coordinate), which would instead count vertical segments and produce a completely different — and wrong — answer.

Solution: Always key the Counter on point[1]:

y_count = Counter(point[1] for point in points)   # group by y, not x

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap: