LeetCode 3623 - Count Number of Trapezoids I

LeetCode Problem 3623

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Math, Geometry

Solution

Problem Understanding

The problem asks us to count the number of horizontal trapezoids that can be formed from a set of points in 2D Cartesian space. A horizontal trapezoid is defined as a convex quadrilateral that has at least one pair of horizontal sides, meaning two sides are parallel to the x-axis. Since two sides are horizontal, they share the same y-coordinate.

The input points is a 2D array of integers where each element [xi, yi] represents the coordinates of a unique point. We are asked to select four distinct points to form a trapezoid and return the total number modulo 10^9 + 7.

Constraints are significant: points.length can go up to 10^5, and coordinates can be very large, from -10^8 to 10^8. This rules out brute-force enumeration of all quadruples, which would be O(n^4) and infeasible. The guarantee that all points are distinct simplifies bookkeeping and prevents zero-area degeneracies due to duplicate points.

Important edge cases include when all points lie on a single horizontal line, when points are sparse along the y-axis, or when there are exactly four points.

Approaches

The brute-force approach is straightforward: iterate over all combinations of four points, compute the slopes of all sides, and check if there is at least one pair of horizontal sides. This guarantees correctness but is too slow because the number of quadruples is O(n^4).

The key insight for an optimal solution is that a horizontal trapezoid requires two horizontal lines, each containing at least one point. If we group points by their y-coordinate, a horizontal side corresponds to a combination of two points on the same y-level. Then, counting trapezoids reduces to counting pairs of points on one horizontal line and pairs of points on another horizontal line.

Formally, for each y-coordinate with k points, there are C(k, 2) ways to choose a horizontal side. If another y-level has l points, we can pair sides from the first and second levels to form trapezoids. Summing over all pairs of distinct y-levels gives the total number of trapezoids. Using this method avoids iterating over all quadruples, reducing the complexity significantly.

Here, H is the number of unique y-values. Since H <= n, this approach scales efficiently for n up to 10^5.

Algorithm Walkthrough

1. Group points by y-coordinate. Iterate through all points and create a dictionary mapping each y-coordinate to a list of x-coordinates at that level.
2. Compute the number of horizontal pairs per level. For each y-coordinate with k points, compute C(k, 2) = k * (k - 1) / 2. This gives the number of horizontal sides that can be formed at that y-coordinate.
3. Combine horizontal pairs from two distinct y-levels. For each pair of distinct y-coordinates y1 and y2, multiply the number of horizontal pairs at y1 with the number at y2. This represents all trapezoids formed using a horizontal side from y1 and one from y2.
4. Sum the counts and take modulo. Accumulate the total trapezoids over all y-level pairs and return the result modulo 10^9 + 7.

Why it works: Each trapezoid requires exactly one pair of points on a horizontal line at the top and one pair on a horizontal line at the bottom. By grouping points by y-coordinate, computing all possible horizontal pairs, and combining them, we enumerate all valid trapezoids exactly once.

Python Solution

from collections import defaultdict
from typing import List

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