Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

A horizontal trapezoid is determined by choosing two points on one horizontal line and two on another. Each pair forms one horizontal side, and different heights ensure the four points form a nondegenerate convex quadrilateral. Count pairs at each height, then combine heights without enumerating them all.

Approach

Count points by y-coordinate. A height containing v points offers C(v, 2) horizontal segments. Maintain the total number of segments from previously processed heights. For the current height, add its segment count multiplied by that running total, then include its segments in the total.

Perform the arithmetic modulo 1,000,000,007. Every pair of distinct heights is combined exactly once, regardless of map iteration order. Parallelograms are included because the problem allows at least one pair of parallel sides; their horizontal bases still identify only one counted height pair.

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        MOD = 10**9 + 7
        hl = defaultdict(int)
        for x, y in points:
            hl[y] += 1

        res = 0
        prev = 0
        for v in hl.values():
            curr = comb(v, 2)
            res = (res + curr * prev) % MOD
            prev = (prev + curr) % MOD

        return res

Complexity analysis

Let n = points.length and u be the number of distinct y-coordinates. Time: O(n + u). Auxiliary space: O(u).