Skip to main content
Talentd

Count Number of Trapezoids I - Solution & Explanation

MediumArrayHash TableMathGeometry10 min readAsked at: Meta, Google, Bloomberg
Practice this problem

Problem Statement

You are given a 2D integer array points, where points[i] = [xi, yi] represents the coordinates of the ith 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 109 + 7.

 

Example 1:

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

Output: 3

Explanation:

There are three distinct ways to pick four points that form a horizontal trapezoid:

  • Using points [1,0], [2,0], [3,2], and [2,2].
  • Using points [2,0], [3,0], [3,2], and [2,2].
  • Using points [1,0], [3,0], [3,2], and [2,2].

Example 2:

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

Output: 1

Explanation:

There is only one horizontal trapezoid that can be formed.

 

Constraints:

  • 4 <= points.length <= 105
  • –108 <= xi, yi <= 108
  • All points are pairwise distinct.

Approach Overview

Problem Overview: You are given points on a 2D plane. A trapezoid requires at least one pair of parallel sides. The key observation is that any pair of points sharing the same y-coordinate forms a horizontal segment, and two horizontal segments on different y levels can act as the parallel sides of a trapezoid.

Approach 1: Enumeration with Y-Level Grouping (O(n + k2) time, O(n) space)

Group points by their y-coordinate using a hash map. If a level has m points, you can form C(m,2) horizontal segments on that line. Each segment represents a possible base of a trapezoid. Store the number of segments for every y-level.

Next, enumerate every pair of distinct y-levels. If level i has a horizontal segments and level j has b, then you can form a * b trapezoids using one segment from each level as the parallel sides. The non-parallel sides are implicitly defined by connecting the endpoints. Summing this product across all pairs of levels gives the total trapezoid count.

The hash table groups points efficiently, while simple array enumeration handles combinations of levels. The geometric insight is that parallel horizontal segments guarantee a trapezoid regardless of the remaining edges. This reduces a geometric counting problem to a combination counting problem using math and hashing.

Space complexity is O(n) to store the frequency of points per y-level. Time complexity is dominated by counting segments and iterating over pairs of distinct levels. If there are k unique y-coordinates, the pair enumeration costs O(k^2).

Recommended for interviews: The hash map + enumeration approach is the expected solution. It shows you can convert a geometry problem into counting combinations. A brute force check of all quadruples of points would be O(n^4) and only demonstrates baseline understanding, while grouping by y-coordinate and counting segment pairs shows stronger algorithmic reasoning.

Solution

According to the problem description, horizontal edges have the same y coordinate. Therefore, we can group points by their y coordinates and count the number of points for each y coordinate.

We use a hash table cnt to store the number of points for each y coordinate. For each y coordinate y_i, assuming the number of corresponding points is v, the number of ways to select two points from these points as a horizontal edge is \binom{v}{2} = \frac{v(v-1)}{2}, denoted as t.

We use a variable s to record the sum of the number of horizontal edges for all previous y coordinates. Then, we can multiply the number of horizontal edges t for the current y coordinate by the sum s of the number of horizontal edges for all previous y coordinates to get the number of trapezoids with the current y coordinate as one pair of horizontal edges, and add it to the answer. Finally, we add the number of horizontal edges t for the current y coordinate to s for subsequent calculations.

Note that since the answer may be very large, we need to take the modulo 10^9 + 7.

The time complexity is O(n) and the space complexity is O(n), where n is the number of points.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Quadruple EnumerationO(n^4)O(1)Conceptual baseline; useful for verifying small inputs
Enumerate All Segments and Check ParallelismO(n^2)O(n^2)General geometry problems where slopes must be compared
Hash Map by Y-Level + Segment Pair EnumerationO(n + k^2)O(n)Optimal for horizontal parallel sides; typical interview solution

Video Solution

Count Number of Trapezoids I | Simplest Explanation | Detailed | Leetcode 3623 | codestorywithMIK • codestorywithMIK • 7,521 views views

Watch 9 more video solutions →

Frequently Asked Questions

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).

Ready to solve this problem?

Practice Count Number of Trapezoids I with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays