Is Count Number of Trapezoids I easy or hard?

Count Number of Trapezoids I is typically classified as Medium difficulty. The challenge is recognizing that trapezoids can be counted by grouping horizontal segments and applying combinatorics rather than explicitly constructing quadrilaterals.

Count Number of Trapezoids I Python/Java solution

Most implementations first build a hash map from y-coordinate to point count. Then compute combinations C(m,2) for each level and iterate through pairs of levels multiplying their segment counts. The same logic translates directly to Python, Java, C++, Go, and TypeScript.

How to solve Count Number of Trapezoids I in O(n)?

Strict O(n) is generally not achievable because you must consider combinations of distinct y-levels. The closest practical solution is O(n + k^2) by grouping points by y-coordinate and counting horizontal segments. Pairing segment counts across levels efficiently counts all trapezoids.

What is the best approach for Count Number of Trapezoids I?

The most efficient approach groups points by their y-coordinate using a hash map. For each y-level with m points, compute C(m,2) horizontal segments. Then enumerate pairs of y-levels and multiply their segment counts to get the number of trapezoids. This reduces the geometric problem to combination counting with O(n + k^2) time.

Is Count Number of Trapezoids I asked at Google/Amazon/Meta?

Geometry counting problems involving hash maps and combinations appear in interviews at companies like Google, Amazon, and Meta. Variations often test whether candidates can transform geometric constraints into frequency counting or combinatorial formulas.

What data structure is used in Count Number of Trapezoids I?

A hash table (hash map) is the primary data structure. It stores the number of points for each y-coordinate, allowing quick calculation of horizontal segment counts and efficient enumeration of level pairs.

What is the time complexity of Count Number of Trapezoids I?

The optimized solution runs in O(n + k^2) time where n is the number of points and k is the number of unique y-coordinates. Building the hash map takes O(n), computing segment counts is linear, and enumerating pairs of y-levels costs O(k^2). Space complexity is O(n).

3623. Count Number of Trapezoids I - Practice Online

You are given a 2D integer array points, where points[i] = [x_i, y_i] represents the coordinates of the i^th point on the Cartesian plane.

A horizontal trapezoid is a convex quadrilateral with at least one pair of horizontal sides (i.e. parallel to the x-axis). Two lines are parallel if and only if they have the same slope.

Return the number of unique horizontal trapezoids that can be formed by choosing any four distinct points from points.

Since the answer may be very large, return it modulo 10⁹ + 7.

Example 1:

Input: points = [[1,0],[2,0],[3,0],[2,2],[3,2]]

Output: 3

Explanation: