Editorial

Solution walkthrough

Review the explanation, then compare the reference implementation.

Video explanation

Solution

Intuition

Two segments on distinct parallel lines form opposite sides of a trapezoid. Counting all such segment pairs counts ordinary trapezoids once, but parallelograms twice because both pairs of opposite sides are parallel. Subtract one count per parallelogram.

Approach

Enumerate every point pair. Group its segment by slope and supporting-line intercept, using a special vertical slope and the x-coordinate as its intercept. Also group segments by doubled midpoint and slope; doubled integer coordinates avoid dividing midpoint coordinates.

For each slope, count pairs of segments belonging to different intercept groups. Python multiplies each group size by a running sum of earlier sizes. JavaScript subtracts same-intercept pairs from all pairs in the slope bucket. Distinct lines exclude degenerate collinear configurations.

Next, for each midpoint, similarly count segment pairs with different slopes and subtract that count. Such segments are the diagonals of a nondegenerate parallelogram because they bisect each other. Different slopes exclude collinear diagonals, and each parallelogram has one unique diagonal pair. This leaves every trapezoid counted once. Both implementations use numeric slope and intercept keys for the problem's bounded integer coordinates.

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

        for i in range(n):
            x1, y1 = points[i]
            for j in range(i + 1, n):
                x2, y2 = points[j]
                dx, dy = x2 - x1, y2 - y1
                if dx != 0:
                    s = dy / dx
                    b = (y1 * dx - x1 * dy) / dx
                else:
                    s = inf
                    b = x1
                s_i[s].append(b)
                mid = (x1 + x2, y1 + y2)
                m_s[mid].append(s)

        res = 0

        for intercepts_in_same_slope in s_i.values():
            if len(intercepts_in_same_slope) == 1: continue
            c = Counter(intercepts_in_same_slope)
            acc = 0
            for count in c.values():
                res += acc * count
                acc += count

        for slopes_in_same_mid in m_s.values():
            if len(slopes_in_same_mid) == 1: continue
            c = Counter(slopes_in_same_mid)
            acc = 0
            for count in c.values():
                res -= acc * count
                acc += count

        return res

Complexity analysis

Let n = points.length. Time: O(n^2). Auxiliary space: O(n^2) for slope/intercept and midpoint/slope buckets.