Count Number of Trapezoids I

main.md

Question

Approach

I observe a horizontal trapezoid must have two horizontal sides (the two parallel bases), so it is formed by picking two distinct y-levels and choosing two points on each of those levels. For each y I compute a_y = C(count_y, 2) (the number of ways to pick an ordered horizontal segment at that y). The number of trapezoids equals the number of unordered pairs of different levels multiplied: sum_{i<j} a_i * a_j.

Implementation

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        MOD = 10**9 + 7
        cnt = Counter(y for x, y in points)
        
        a_vals = []
        for c in cnt.values():
            if c >= 2:
                a_vals.append((c * (c - 1)) // 2)
        
        if not a_vals:
            return 0
        
        sum_a = sum(a_vals) % MOD
        sum_sq = sum((x % MOD) * (x % MOD) for x in a_vals) % MOD
        
        ans = (sum_a * sum_a - sum_sq) % MOD
        inv2 = (MOD + 1) // 2
        ans = (ans * inv2) % MOD
        return ans

Complexities

• Time: O(n)
• Space: O(m) where m is the number of distinct y-values