3625. Count Number of Trapezoids II

HardGeometryArrayHash 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ᵗʰ 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.

In other words, your task is to count how many groups of four distinct points can be arranged into a convex quadrilateral such that at least one pair of its opposite sides are parallel. Since two sides are parallel exactly when they share the same slope, you need to look for pairs of point-pairs that have equal slopes but lie on different lines (so that they form two distinct parallel sides rather than the same line). Care must also be taken with parallelograms, which have two pairs of parallel sides and could therefore be counted more than once.

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 point-pairs by slope and intercept, counts parallel segments across different lines, and subtracts double-counted parallelograms using midpoint grouping.

Open in Flowchart

Intuition

The key observation is that a trapezoid needs at least one pair of parallel sides. Two segments are parallel when they have the same slope. So instead of thinking about four points at once, let's think about pairs of points, because every side of a quadrilateral is just a segment connecting two points.

If we enumerate every pair of points and compute the slope of the line through them, then any two pairs that share the same slope could potentially serve as the two parallel sides of a trapezoid. So a natural idea is: group all point-pairs by their slope, and for each slope, count how many ways we can pick two of these parallel segments.

But there is a subtle trap. Two segments with the same slope might actually lie on the same line. In that case the four points are collinear and cannot form a quadrilateral at all. To avoid this, we don't just group by slope k; we also distinguish by the intercept b of the line. Segments with the same slope but different intercepts lie on different parallel lines, which is exactly what we want. So within each slope group, we further split by intercept, and only count pairs of segments coming from different intercepts.

This is where the counting trick comes in. For a fixed slope k, suppose the intercepts have occurrence counts t₁, t₂, t₃, .... The number of valid cross-intercept pairs can be computed by sweeping through the counts: keep a running sum s of everything seen so far, and for each new count t, add s * t to the answer. This efficiently counts all pairs that come from two different intercepts without double-counting.

Now comes the second subtlety: parallelograms. A parallelogram has two pairs of parallel sides. When we count by "pairs of parallel segments," a parallelogram gets counted twice, once for each pair of parallel sides. Since the problem asks for unique trapezoids, we must subtract these extra counts once.

How do we detect a parallelogram? A quadrilateral is a parallelogram exactly when its diagonals share the same midpoint. So we again enumerate all point-pairs, but this time we treat each pair as a potential diagonal. We group pairs by their midpoint, and within the same midpoint, two pairs form a parallelogram. To make sure we don't accidentally count degenerate cases (where the points are collinear), we additionally distinguish by slope within each midpoint group. Using the same sweep-and-accumulate trick, we count these parallelograms and subtract them from the answer.

Putting it together: encode the midpoint as a single number p = (x₁ + x₂ + 2000) * 4000 + (y₁ + y₂ + 2000), where the +2000 offsets keep the values non-negative so they can be safely used as hash keys. The final answer is the total parallel-pair count minus the parallelogram count, which gives us exactly the number of unique trapezoids.

Pattern Learn more about Math patterns.

Solution Approach

We use the Hash Table + Enumeration pattern. The core idea is to enumerate all pairs of points and record two kinds of information using two hash tables.

Data structures. We set up two nested hash tables:

cnt1: maps a slope k to another hash table that records, for each intercept b, how many segments with slope k lie on the line with that intercept. So the structure is k -> (b -> count).
cnt2: maps a midpoint code p to another hash table that records, for each slope k, how many point-pairs share that midpoint with that slope. So the structure is p -> (k -> count).

Both are built with defaultdict(lambda: defaultdict(int)) so we can increment counts without checking for existence.

Enumerating point pairs. Let n = len(points). We loop over all unordered pairs (i, j) with j < i. For each pair (x1, y1) and (x2, y2), we compute dx = x2 - x1 and dy = y2 - y1:

If dx == 0, the two points lie on the same vertical line. We use a sentinel slope k = 1e9 and set the intercept b = x1 (the line is x = x1).
Otherwise, the slope is k = dy / dx. The intercept is computed as b = (y1 * dx - x1 * dy) / dx. This comes from rearranging the line equation so that segments on the same line share the same b.

We then update cnt1[k][b] += 1.

For the parallelogram detection, we encode the midpoint of the pair as a single integer:

p = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000)

The +2000 offsets keep both coordinate sums non-negative, and multiplying the x-part by 4000 guarantees that distinct midpoints map to distinct codes (since each coordinate sum fits within a 4000-wide range). We then update cnt2[p][k] += 1.

Counting parallel-side pairs. We iterate over each slope group in cnt1. Within a single slope k, we want to count pairs of segments that have different intercepts. We do this with a running-sum sweep:

for e in cnt1.values():
    s = 0
    for t in e.values():
        ans += s * t
        s += t

Here s accumulates the total count of segments seen so far (from earlier intercepts), and t is the count for the current intercept. Multiplying s * t gives the number of cross-intercept pairs introduced by this intercept, which is exactly the number of valid trapezoid-forming parallel pairs for that slope. This avoids pairing a segment with another segment on the same line.

Subtracting parallelograms. Each parallelogram has two pairs of parallel sides, so it was counted twice above. We subtract one count per parallelogram using cnt2. A parallelogram is identified by two diagonals sharing the same midpoint and same slope grouping. We apply the identical sweep, but subtract this time:

for e in cnt2.values():
    s = 0
    for t in e.values():
        ans -= s * t
        s += t

For a fixed midpoint p, pairing point-pairs with the same midpoint forms parallelograms, and s * t counts these combinations. Distinguishing by slope k inside each midpoint group keeps degenerate collinear cases consistent with how they were counted in cnt1.

Final answer. After adding all parallel-pair counts and subtracting the duplicate parallelogram counts, ans holds the number of unique trapezoids, which we return.

Complexity. Let n be the number of points. We enumerate O(n²) pairs, and each insertion into the hash tables is O(1) on average. The final sweeps over the hash table entries also total O(n²). Thus the time complexity is O(n²), and the space complexity is O(n²) to store all the point-pair entries.

Example Walkthrough

Let's use a small set of 5 points that contains both a "pure" trapezoid and a parallelogram, so we can see every part of the algorithm working — including the parallelogram subtraction.

points = [
  [0, 0],   # P0
  [4, 0],   # P1
  [1, 2],   # P2
  [3, 2],   # P3
  [5, 2],   # P4
]

Here is the picture (y grows upward):

y=2:      P2(1,2)   P3(3,2)   P4(5,2)
y=0:  P0(0,0)             P1(4,0)

Our goal is to count unique convex quadrilaterals with at least one pair of parallel sides.

Step 1 — Enumerate all point-pairs, fill `cnt1` (slope → intercept → count)

For each unordered pair we compute dx, dy, then slope k = dy/dx and intercept b = (y1·dx − x1·dy)/dx. (Vertical pairs use sentinel k = 1e9, b = x.)

Pair	(dx, dy)	slope `k`	intercept `b`
P0–P1	(4, 0)	0	0
P0–P2	(1, 2)	2	0
P0–P3	(3, 2)	2/3	0
P0–P4	(5, 2)	2/5	0
P1–P2	(−3, 2)	−2/3	8/3
P1–P3	(−1, 2)	−2	8
P1–P4	(1, 2)	2	−8
P2–P3	(2, 0)	0	2
P2–P4	(4, 0)	0	2
P3–P4	(2, 0)	0	2

Now group into cnt1 as k -> (b -> count):

slope  0    : { b=0 : 1 (P0P1),  b=2 : 3 (P2P3, P2P4, P3P4) }
slope  2    : { b=0 : 1 (P0P2),  b=-8 : 1 (P1P4) }
slope  2/3  : { b=0 : 1 (P0P3) }
slope  2/5  : { b=0 : 1 (P0P4) }
slope -2/3  : { b=8/3 : 1 (P1P2) }
slope -2    : { b=8 : 1 (P1P3) }

Step 2 — Count parallel-side pairs (the running-sum sweep)

For each slope, sweep its intercept counts keeping running sum s, adding s·t:

slope 0: intercepts have counts [1, 3]
- s=0, t=1 → add 0, then s=1
- t=3 → add 1·3 = 3, then s=4
- contributes 3
slope 2: counts [1, 1]
- t=1 → add 0, s=1
- t=1 → add 1·1 = 1
- contributes 1
all other slopes have a single intercept group → contribute 0

Running total ans = 3 + 1 = 4.

These 4 candidate parallel pairs are:

P0P1 ∥ P2P3 (slope 0)
P0P1 ∥ P2P4 (slope 0)
P0P1 ∥ P3P4 (slope 0)
P0P2 ∥ P1P4 (slope 2)

Each represents a quadrilateral with one pair of parallel sides.

Step 3 — Detect parallelograms via `cnt2` (midpoint → slope → count)

A parallelogram's diagonals share the same midpoint. We treat each pair as a diagonal, encode its midpoint as p = (x1+x2+2000)·4000 + (y1+y2+2000), and group by (midpoint, slope).

Look at candidate #4: points P0(0,0), P2(1,2), P1(4,0), P4(5,2).

P2(1,2)        P4(5,2)
   P0(0,0)        P1(4,0)

This is a parallelogram (P0P2 ∥ P1P4 and P0P1 ∥ P2P4). So it was counted twice in Step 2 — once as candidate #2 (P0P1 ∥ P2P4) and once as candidate #4 (P0P2 ∥ P1P4).

Its diagonals are P0–P4 and P1–P2:

P0–P4 midpoint sum = (0+5, 0+2) = (5, 2), slope = 2/5
P1–P2 midpoint sum = (4+1, 0+2) = (5, 2), slope = −2/3

Both share the same encoded midpoint p, so in cnt2:

midpoint(5,2) : { slope 2/5 : 1 (P0P4),  slope -2/3 : 1 (P1P2) }

(No other pairs share a midpoint here, so every other cnt2 group has a single entry.)

Sweep cnt2 the same way:

midpoint(5,2): counts [1, 1] → add 1·1 = 1
everything else contributes 0

So we subtract 1: ans = 4 − 1 = 3.

Step 4 — Final answer

ans = 4 (parallel pairs) − 1 (parallelogram double-count) = 3

The 3 unique trapezoids are:

P0, P1, P2, P3
P0, P1, P2, P4 ← this is the parallelogram (counted once, correctly)
P0, P1, P3, P4

The double-counting of the parallelogram (candidate #2 vs. #4) has been collapsed into a single valid quadrilateral, giving the correct count of 3.

Solution Implementation

1class Solution:
2    def countTrapezoids(self, points: List[List[int]]) -> int:
3        n = len(points)
4
5        # slope_to_intercept_count: slope -> (intercept -> number of segments)
6        # Groups segments by slope; within each slope, groups by intercept.
7        # Two segments sharing the same slope but different intercepts form a
8        # pair of parallel sides (a candidate trapezoid).
9        slope_to_intercept_count: Dict[float, Dict[float, int]] = defaultdict(lambda: defaultdict(int))
10
11        # midpoint_to_slope_count: midpoint key -> (slope -> number of segments)
12        # Groups segments by their midpoint; within each midpoint, groups by slope.
13        # Two segments sharing the same midpoint and the same slope are collinear
14        # through that midpoint and must be excluded to avoid over-counting
15        # (they cannot form a valid trapezoid with each other).
16        midpoint_to_slope_count: Dict[int, Dict[float, int]] = defaultdict(lambda: defaultdict(int))
17
18        for i in range(n):
19            x1, y1 = points[i]
20            for j in range(i):
21                x2, y2 = points[j]
22                dx, dy = x2 - x1, y2 - y1
23
24                if dx == 0:
25                    # Vertical segment: use a sentinel slope and the x-value as intercept.
26                    slope = 1e9
27                    intercept = x1
28                else:
29                    # Line slope and a normalized intercept derived from point-slope form.
30                    slope = dy / dx
31                    intercept = (y1 * dx - x1 * dy) / dx
32
33                slope_to_intercept_count[slope][intercept] += 1
34
35                # Encode the (doubled) midpoint into a single integer key.
36                # Offset by 2000 to keep coordinates non-negative, then pack with base 4000.
37                midpoint_key = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000)
38                midpoint_to_slope_count[midpoint_key][slope] += 1
39
40        answer = 0
41
42        # Count all unordered pairs of segments that are parallel (same slope).
43        # For each slope group, sum over intercept buckets multiplying running
44        # prefix count by the current bucket size to count cross pairs.
45        for intercept_count in slope_to_intercept_count.values():
46            prefix = 0
47            for count in intercept_count.values():
48                answer += prefix * count
49                prefix += count
50
51        # Subtract pairs that share both midpoint and slope, since these are
52        # collinear/degenerate and were incorrectly counted above.
53        for slope_count in midpoint_to_slope_count.values():
54            prefix = 0
55            for count in slope_count.values():
56                answer -= prefix * count
57                prefix += count
58
59        return answer
60

1class Solution {
2    public int countTrapezoids(int[][] points) {
3        int n = points.length;
4
5        // lineMap groups segments by their line definition.
6        // Key: slope (k) -> { intercept (b) -> count of segments lying on that line }
7        // Two segments sharing the same slope and intercept are collinear (on the same line),
8        // while segments sharing only the slope are parallel (potential trapezoid sides).
9        Map<Double, Map<Double, Integer>> lineMap = new HashMap<>(n * n);
10
11        // midpointMap groups segments by their midpoint.
12        // Key: encoded midpoint -> { slope (k) -> count of segments with that midpoint }
13        // Segments sharing the same midpoint but different slopes form the diagonals
14        // of a parallelogram, which must be subtracted to avoid over-counting.
15        Map<Integer, Map<Double, Integer>> midpointMap = new HashMap<>(n * n);
16
17        for (int i = 0; i < n; i++) {
18            int x1 = points[i][0];
19            int y1 = points[i][1];
20
21            for (int j = 0; j < i; j++) {
22                int x2 = points[j][0];
23                int y2 = points[j][1];
24
25                int dx = x2 - x1;
26                int dy = y2 - y1;
27
28                // Compute the slope (k). Use Double.MAX_VALUE to represent a vertical line.
29                double slope = (dx == 0) ? Double.MAX_VALUE : 1.0 * dy / dx;
30
31                // Compute the intercept (b). For a vertical line, use the x-coordinate;
32                // otherwise derive the y-intercept from the line equation.
33                double intercept = (dx == 0) ? x1 : 1.0 * (y1 * dx - x1 * dy) / dx;
34
35                // Normalize negative zero to positive zero so map keys match correctly.
36                if (slope == -0.0) {
37                    slope = 0.0;
38                }
39                if (intercept == -0.0) {
40                    intercept = 0.0;
41                }
42
43                // Record this segment under its line (slope + intercept).
44                lineMap.computeIfAbsent(slope, key -> new HashMap<>())
45                       .merge(intercept, 1, Integer::sum);
46
47                // Encode the midpoint (scaled and offset to keep it a positive integer key).
48                // Offsetting by 2000 and scaling by 4000 maps the midpoint sum into a unique value.
49                int encodedMidpoint = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000);
50
51                // Record this segment under its midpoint, keyed by slope.
52                midpointMap.computeIfAbsent(encodedMidpoint, key -> new HashMap<>())
53                           .merge(slope, 1, Integer::sum);
54            }
55        }
56
57        int ans = 0;
58
59        // Count pairs of parallel segments (same slope, different lines).
60        // For each slope group, pair segments across different intercepts.
61        // Using a running prefix sum 's', each new group of 't' segments
62        // pairs with all previously seen segments.
63        for (Map<Double, Integer> segmentsByIntercept : lineMap.values()) {
64            int prefixSum = 0;
65            for (int count : segmentsByIntercept.values()) {
66                ans += prefixSum * count;
67                prefixSum += count;
68            }
69        }
70
71        // Subtract pairs of segments sharing the same midpoint (parallelogram diagonals).
72        // These pairs were incorrectly counted as trapezoids and must be removed,
73        // since they actually form parallelograms rather than (proper) trapezoids.
74        for (Map<Double, Integer> segmentsBySlope : midpointMap.values()) {
75            int prefixSum = 0;
76            for (int count : segmentsBySlope.values()) {
77                ans -= prefixSum * count;
78                prefixSum += count;
79            }
80        }
81
82        return ans;
83    }
84}
85

1class Solution {
2public:
3    int countTrapezoids(vector<vector<int>>& points) {
4        int n = points.size();
5
6        // lineGroups: groups segments by their line slope (k) and intercept (b).
7        //   key   = slope k
8        //   value = map from intercept b -> number of segments lying on that exact line
9        // Segments sharing the same slope k but different intercept b are parallel
10        // (and distinct), which is the basis for forming trapezoids.
11        unordered_map<double, unordered_map<double, int>> lineGroups;
12
13        // midpointGroups: groups segments by their midpoint and slope.
14        //   key   = encoded midpoint position
15        //   value = map from slope k -> number of segments with that midpoint and slope
16        // This is used to subtract parallelograms, which share both midpoint and slope
17        // for opposite sides and would otherwise be incorrectly counted as trapezoids.
18        unordered_map<int, unordered_map<double, int>> midpointGroups;
19
20        lineGroups.reserve(n * n);
21        midpointGroups.reserve(n * n);
22
23        // Enumerate every unordered pair of points (i, j) to form a candidate segment.
24        for (int i = 0; i < n; ++i) {
25            int x1 = points[i][0], y1 = points[i][1];
26            for (int j = 0; j < i; ++j) {
27                int x2 = points[j][0], y2 = points[j][1];
28
29                int dx = x2 - x1, dy = y2 - y1;
30
31                // Slope of the segment. Use a sentinel large value for vertical lines
32                // (dx == 0) to keep them in a distinct slope bucket.
33                double slope = (dx == 0 ? 1e9 : 1.0 * dy / dx);
34
35                // Intercept of the line containing the segment.
36                // For vertical lines, use the x-coordinate as the distinguishing value.
37                // Otherwise compute b = y1 - slope * x1, rearranged to avoid precision loss:
38                //   b = (y1 * dx - x1 * dy) / dx
39                double intercept = (dx == 0
40                                        ? x1
41                                        : 1.0 * (1LL * y1 * dx - 1LL * x1 * dy) / dx);
42
43                // Record this segment under its line (slope, intercept).
44                lineGroups[slope][intercept] += 1;
45
46                // Encode the (doubled) midpoint into a single integer key.
47                // Offsets (+2000) keep the values non-negative, and the multiplier
48                // (4000) separates the x and y components without collision.
49                int midpointKey = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000);
50
51                // Record this segment under its midpoint and slope.
52                midpointGroups[midpointKey][slope] += 1;
53            }
54        }
55
56        int ans = 0;
57
58        // Count pairs of parallel segments (same slope, different intercept).
59        // Within each slope group, for every intercept bucket, combine its segment
60        // count with the running total of previously seen segments. Each such pair
61        // of parallel, non-collinear segments forms a trapezoid candidate.
62        for (auto& [_, interceptCounts] : lineGroups) {
63            int prefixSum = 0;
64            for (auto& [_, count] : interceptCounts) {
65                ans += prefixSum * count;
66                prefixSum += count;
67            }
68        }
69
70        // Subtract parallelograms. Two parallel segments that also share the same
71        // midpoint form the diagonals/opposite sides of a parallelogram, which should
72        // not be counted as a (strict) trapezoid. Apply the same pairing logic per
73        // midpoint group and remove those over-counted pairs.
74        for (auto& [_, slopeCounts] : midpointGroups) {
75            int prefixSum = 0;
76            for (auto& [_, count] : slopeCounts) {
77                ans -= prefixSum * count;
78                prefixSum += count;
79            }
80        }
81
82        return ans;
83    }
84};
85

1/**
2 * Counts the number of trapezoids that can be formed from a set of points.
3 * A trapezoid is defined by having at least one pair of parallel sides.
4 *
5 * Strategy:
6 *  1. For every pair of points, compute the line segment's slope and intercept.
7 *  2. Group segments by slope, then by intercept. Pairs of segments with the
8 *     same slope but different intercepts are parallel (forming trapezoid sides).
9 *  3. Segments sharing the same midpoint AND slope form a parallelogram's
10 *     diagonals, which leads to overcounting; subtract those cases.
11 *
12 * @param points - Array of [x, y] coordinates.
13 * @returns The number of valid trapezoids.
14 */
15function countTrapezoids(points: number[][]): number {
16    const pointCount: number = points.length;
17
18    // slopeToInterceptCount: slope -> (intercept -> number of segments)
19    // Used to count pairs of parallel (non-collinear) segments.
20    const slopeToInterceptCount: Map<number, Map<number, number>> = new Map();
21
22    // midpointToSlopeCount: encoded midpoint -> (slope -> number of segments)
23    // Used to detect and subtract parallelogram-diagonal overcounts.
24    const midpointToSlopeCount: Map<number, Map<number, number>> = new Map();
25
26    // Iterate over every unordered pair of points (i, j) with j < i.
27    for (let i = 0; i < pointCount; i++) {
28        const [x1, y1] = points[i];
29        for (let j = 0; j < i; j++) {
30            const [x2, y2] = points[j];
31            const [deltaX, deltaY] = [x2 - x1, y2 - y1];
32
33            // Slope of the segment. Use a sentinel (1e9) for vertical lines.
34            const slope: number = deltaX === 0 ? 1e9 : deltaY / deltaX;
35
36            // Normalized intercept. For vertical lines, use the x-coordinate;
37            // otherwise compute (y1 * dx - x1 * dy) / dx to keep precision consistent.
38            const intercept: number =
39                deltaX === 0 ? x1 : (y1 * deltaX - x1 * deltaY) / deltaX;
40
41            // Record this segment under its slope and intercept.
42            if (!slopeToInterceptCount.has(slope)) {
43                slopeToInterceptCount.set(slope, new Map());
44            }
45            const interceptCount: Map<number, number> =
46                slopeToInterceptCount.get(slope)!;
47            interceptCount.set(intercept, (interceptCount.get(intercept) || 0) + 1);
48
49            // Encode the midpoint (scaled by 2 to avoid fractions) into a single key.
50            // Offsets (+2000) and multiplier (4000) keep values positive and unique.
51            const midpointKey: number =
52                (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000);
53
54            // Record this segment under its midpoint and slope.
55            if (!midpointToSlopeCount.has(midpointKey)) {
56                midpointToSlopeCount.set(midpointKey, new Map());
57            }
58            const slopeCount: Map<number, number> =
59                midpointToSlopeCount.get(midpointKey)!;
60            slopeCount.set(slope, (slopeCount.get(slope) || 0) + 1);
61
62        }
63    }
64
65    let answer: number = 0;
66
67    // Add up pairs of parallel segments grouped by slope.
68    // For each distinct intercept group, multiply its count with the running
69    // sum of previously seen counts to accumulate cross-group pairs.
70    for (const interceptCount of slopeToInterceptCount.values()) {
71        let runningSum: number = 0;
72        for (const count of interceptCount.values()) {
73            answer += runningSum * count;
74            runningSum += count;
75        }
76    }
77
78    // Subtract overcounted parallelogram cases: segments that share both a
79    // midpoint and a slope are diagonals of a parallelogram and were
80    // double-counted as parallel pairs above.
81    for (const slopeCount of midpointToSlopeCount.values()) {
82        let runningSum: number = 0;
83        for (const count of slopeCount.values()) {
84            answer -= runningSum * count;
85            runningSum += count;
86        }
87    }
88
89    return answer;
90}
91

Time and Space Complexity

Time Complexity: O(n^2)

The core of the algorithm is the double loop iterating over all pairs of points:
```
for i in range(n):
    for j in range(i):
        ...
```
This nested loop runs C(n, 2) = n * (n - 1) / 2 times, which is O(n^2). Each iteration performs constant-time work: computing the slope k, intercept b, midpoint key p, and updating the dictionaries cnt1 and cnt2 in O(1).

After the loops, the code aggregates results by traversing the dictionaries:
```
for e in cnt1.values():
    for t in e.values():
        ...
for e in cnt2.values():
    for t in e.values():
        ...
```
Since each pair of points contributes exactly one entry across all the inner dictionaries of cnt1 (and likewise for cnt2), the total number of elements traversed is bounded by the number of pairs, i.e., O(n^2). Therefore, the overall time complexity is O(n^2).
Space Complexity: O(n^2)

The dictionaries cnt1 and cnt2 store information for each of the O(n^2) point pairs. In the worst case, each pair maps to a distinct key, so the total number of entries stored across cnt1 and cnt2 is proportional to the number of pairs, giving O(n^2) space.

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

Common Pitfalls

Pitfall 1: Using floating-point slope and intercept as hash keys

The most dangerous trap in this solution is representing both the slope and intercept as float values (via dy / dx and (y1 * dx - x1 * dy) / dx).

Why it's a problem:

Floating-point division introduces rounding errors. Two segments that are mathematically parallel (or collinear) may produce slightly different float values, such as 0.3333333333333333 vs 0.33333333333333337. They would then fall into different hash buckets, causing the algorithm to miss valid parallel pairs or fail to subtract a parallelogram.
Conversely, two genuinely different slopes might collide to the same float after rounding, inflating the count.
The sentinel value 1e9 for vertical lines is fragile: if any real slope happens to equal 1e9 (unlikely but conceptually unsafe), the logic breaks. It also mixes a "magic number" with legitimate computed slopes.

Solution: Use an exact rational representation by storing the slope as a reduced integer pair (dy/g, dx/g) where g = gcd(dx, dy), with a normalized sign. Do the same for the intercept by keeping it as an integer-pair fraction rather than dividing.

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        from math import gcd
        n = len(points)
        slope_to_intercept_count = defaultdict(lambda: defaultdict(int))
        midpoint_to_slope_count = defaultdict(lambda: defaultdict(int))

        for i in range(n):
            x1, y1 = points[i]
            for j in range(i):
                x2, y2 = points[j]
                dx, dy = x2 - x1, y2 - y1

                # Normalize slope to an exact, canonical (dy, dx) pair.
                g = gcd(dx, dy)
                sdx, sdy = dx // g, dy // g
                if sdx < 0 or (sdx == 0 and sdy < 0):
                    sdx, sdy = -sdx, -sdy
                slope = (sdy, sdx)  # exact, hashable

                # Exact intercept: cross-product form is integer and line-invariant.
                # For points on the same line: y1*dx - x1*dy is constant up to scale.
                if sdx == 0:                 # vertical line x = x1
                    intercept = (x1, 0)
                else:
                    # b * dx = y1*dx - x1*dy ; keep as reduced fraction
                    num = y1 * sdx - x1 * sdy
                    intercept = (num, sdx)

                slope_to_intercept_count[slope][intercept] += 1

                midpoint_key = (x1 + x2, y1 + y2)   # exact integer tuple
                midpoint_to_slope_count[midpoint_key][slope] += 1

        answer = 0
        for bucket in slope_to_intercept_count.values():
            prefix = 0
            for c in bucket.values():
                answer += prefix * c
                prefix += c
        for bucket in midpoint_to_slope_count.values():
            prefix = 0
            for c in bucket.values():
                answer -= prefix * c
                prefix += c
        return answer

Pitfall 2: A brittle midpoint-encoding formula

The original packing (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000) silently assumes every coordinate sum lies in [-2000, 2000) and that 4000 is a large enough base. If the actual constraints allow coordinates whose doubled values exceed this range, different midpoints collide to the same key, corrupting the parallelogram subtraction.

Why it's a problem:

The "magic numbers" 2000 and 4000 are tied to a specific (unstated) constraint. Any input outside that envelope produces wrong answers with no error raised, making the bug very hard to detect.
It couples correctness to constraints that may change between problem versions.

Solution: Use a plain integer tuple (x1 + x2, y1 + y2) as the key (shown above). Tuples are hashable, exact, and never collide regardless of coordinate magnitude—eliminating the magic numbers entirely.

Pitfall 3: Misidentifying what the second sweep subtracts

It's easy to assume the midpoint_to_slope_count sweep subtracts parallelograms (counted twice). In reality, grouping by same midpoint and same slope captures collinear point-pairs (degenerate segments lying on one line through a shared midpoint), which must be removed so they aren't mistaken for two parallel sides.

Why it matters: If you reason about this incorrectly, you might "fix" the wrong sweep—for example, trying to subtract once per parallelogram via the slope/intercept table—and introduce a subtle off-by-one in the count.

Solution: Keep the two responsibilities separate and clearly documented:

The first sweep counts every same-slope, different-intercept pair (all candidate parallel-side pairs).
The second sweep removes degenerate same-midpoint, same-slope collinear configurations that would otherwise be miscounted. Verify the logic against small hand-built cases (e.g., 4 collinear points, a single parallelogram, a single trapezoid) before trusting it.

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:

Which of the tree traversal order can be used to obtain elements in a binary search tree in sorted order?

Pre-order traversal

Post-order traversal

In-order traversal

Level-order traversal

I don't know