#3625

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Number of Trapezoids II

Count Number of Trapezoids II requires scanning point pairs and hashing slopes to efficiently find parallel sides in arrays.

array hash table math geometry

Problem Statement

Given a list of 2D points, each represented as [x, y], determine how many unique trapezoids can be formed using exactly four distinct points. A trapezoid is defined as a convex quadrilateral with at least one pair of sides parallel.

Two sides are parallel if their slopes are equal. Return the total count of all possible trapezoids from the given points list. Points are guaranteed to be distinct, and coordinates range between -1000 and 1000.

Examples

Example 1

Input: points = [[-3,2],[3,0],[2,3],[3,2],[2,-3]]

Output: 2

There are two distinct ways to pick four points that form a trapezoid:

Example 2

Input: points = [[0,0],[1,0],[0,1],[2,1]]

Output: 1

There is only one trapezoid which can be formed.

Constraints

4 <= points.length <= 500
–1000 <= xi, yi <= 1000
All points are pairwise distinct.

Solution Approach

Normalize slopes for all point pairs

Iterate over all unique pairs of points and compute the slope as a fraction reduced by GCD. Fix the sign to keep consistency. Store each pair in a hash map keyed by its slope to quickly locate parallel candidates.

Combine parallel pairs

For each slope group, consider combinations of two pairs that do not share points. Each valid combination corresponds to one trapezoid. This step leverages array scanning and hash lookup to avoid O(n^4) brute force.

Count total trapezoids

Accumulate all valid trapezoid counts from the slope groups. Ensure no duplicates by only pairing disjoint point pairs. Return the final count as the answer.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity depends on generating all point pairs O(n^2) and hashing slopes, then combining pairs which is manageable with hash map groups. Space complexity is O(n^2) for storing slope maps.

What Interviewers Usually Probe

Look for a method to normalize slopes instead of comparing floating points.
Notice that brute-force four-point iteration will exceed time limits for n=500.
Expect hash-based grouping of slopes as the primary optimization.

Common Pitfalls or Variants

Common pitfalls

Failing to reduce slope fractions correctly leads to missed parallel pairs.
Including overlapping point pairs in the same trapezoid counts duplicates.
Using floating-point slope comparisons without normalization causes precision errors.

Follow-up variants

Count trapezoids in 3D by projecting onto planes and hashing direction vectors.
Return all trapezoid coordinates instead of just the count, using the same slope hash approach.
Limit to trapezoids with horizontal bases to simplify slope handling.

FAQ

What is the key pattern to solve Count Number of Trapezoids II efficiently?

The primary pattern is scanning all point pairs and using a hash map keyed by normalized slope to detect parallel sides quickly.

How do I handle slope precision in this problem?

Compute slope as a fraction reduced by GCD and fix signs consistently to avoid floating-point errors.

Can I use a brute-force approach?

Brute-force four-point iteration is too slow for n up to 500; using hash-based slope groups is required for efficiency.

Are overlapping point pairs allowed when counting trapezoids?

No, each trapezoid must use four distinct points; overlapping pairs lead to invalid counts.

How does array scanning plus hash lookup help here?

It allows grouping point pairs by slope and quickly finding combinations that form trapezoids without iterating all quadruples.

terminal

Solution

Solution 1: Hash Table + Enumeration

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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        n = len(points)

        # cnt1: k -> (b -> count)
        cnt1: dict[float, dict[float, int]] = defaultdict(lambda: defaultdict(int))
        # cnt2: p -> (k -> count)
        cnt2: dict[int, dict[float, int]] = 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

                if dx == 0:
                    k = 1e9
                    b = x1
                else:
                    k = dy / dx
                    b = (y1 * dx - x1 * dy) / dx

                cnt1[k][b] += 1

                p = (x1 + x2 + 2000) * 4000 + (y1 + y2 + 2000)
                cnt2[p][k] += 1

        ans = 0

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

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

        return ans

Continue Practicing

#3623 count number of trapezoids i #3588 find maximum area of a triangle #3591 check if any element has prime frequency