How do you solve Count Number of Trapezoids II on LeetCode?

Count Number of Trapezoids II (LeetCode #3625) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n^2) time complexity and O(n) space complexity. Key insight: Trapezoids require parallel sides, which can be identified by slopes.

What is the brute force solution for Count Number of Trapezoids II?

The brute force approach for Count Number of Trapezoids II is Brute Force, with O(n^4) time complexity and O(1) space complexity. Check all combinations of four points to see if they form a trapezoid by calculating slopes. This is straightforward but inefficient. The optimal Optimal Solution approach improves this to O(n^2).

What algorithm or data structure is used to solve Count Number of Trapezoids II?

Count Number of Trapezoids II uses the following concepts: Array, Hash Table, Math, Geometry. The recommended patterns to study are: Hash Map, Array.

What are the interview tips for Count Number of Trapezoids II?

Explain your thought process clearly. Consider edge cases and constraints. Discuss time and space complexity.

What are common mistakes when solving Count Number of Trapezoids II?

Not normalizing slopes correctly (signs and GCD). Counting the same trapezoid multiple times due to different point orders.

#3625

Count Number of Trapezoids II

Hard

ArrayHash TableMathGeometryHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n^4)	O(n^2)
Space	O(1)	O(n)

💡

Intuition

Time O(n^2)Space O(n)

Group points by slopes to find pairs of parallel sides efficiently. This reduces the number of combinations to check.

⚙️

Algorithm

3 steps

1Step 1: Create a hash map to store slopes between all pairs of points.
2Step 2: For each slope, count how many pairs of points share that slope.
3Step 3: For each slope with k pairs, add C(k, 2) to the total count of trapezoids.

solution.py15 lines

1from collections import defaultdict
2from math import gcd
3
4def count_trapezoids(points):
5    slope_map = defaultdict(int)
6    n = len(points)
7    for i in range(n):
8        for j in range(i + 1, n):
9            dy, dx = points[j][1] - points[i][1], points[j][0] - points[i][0]
10            g = gcd(dy, dx)
11            slope_map[(dy // g, dx // g)] += 1
12    count = 0
13    for k in slope_map.values():
14        count += k * (k - 1) // 2
15    return count

ℹ

Complexity note: This complexity comes from iterating through pairs of points to compute slopes, which is significantly more efficient than checking all combinations of four points.

1Trapezoids require parallel sides, which can be identified by slopes.
2Using a hash map to group slopes reduces unnecessary computations.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.