Skip to main content
Talentd

Count Number of Trapezoids II - Solution & Explanation

HardArrayHash TableMathGeometry18 min readAsked at: Meta, Google
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.

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

A trapezoid is a convex quadrilateral with at least one pair of parallel sides. Two lines are parallel if and only if they have the same slope.

 

Example 1:

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

Output: 2

Explanation:

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

  • The points [-3,2], [2,3], [3,2], [2,-3] form one trapezoid.
  • The points [2,3], [3,2], [3,0], [2,-3] form another trapezoid.

Example 2:

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

Output: 1

Explanation:

There is only one trapezoid which can be formed.

 

Constraints:

  • 4 <= points.length <= 500
  • –1000 <= xi, yi <= 1000
  • All points are pairwise distinct.

Approach Overview

Problem Overview: You are given points on a 2D plane and need to count how many unique trapezoids can be formed. A trapezoid is a quadrilateral with at least one pair of parallel sides, so the task reduces to identifying pairs of parallel segments that can act as the bases.

Approach 1: Hash Table + Enumeration (O(n2) time, O(n2) space)

Enumerate every pair of points (i, j) and treat the segment between them as a potential base of a trapezoid. Compute its slope using basic math and normalize it (e.g., reduce the fraction of dy/dx) so parallel segments share the same representation. Use a hash table to group segments by slope.

Inside each slope group, segments lie on many different lines. Two segments can form the parallel sides of a trapezoid only if they belong to different lines (different intercepts) and do not share endpoints. Store additional identifiers such as line intercept or midpoint to distinguish segments. Count how many pairs of segments with the same slope lie on different lines. Each valid pair contributes trapezoids when their endpoints form four distinct vertices.

This converts a geometric constraint into a counting problem. Instead of checking every quadruple of points, you first enumerate all segments in O(n^2), group them with hashing, and then count combinations within each slope bucket. Geometry calculations are simple integer operations, which keeps the approach efficient even for large inputs.

The key insight: trapezoids exist when two segments are parallel but not collinear. Grouping by slope avoids repeated comparisons and lets you count candidates quickly using frequency counts and combinations. This pattern—enumerate pairs, normalize a geometric property, and aggregate with hashing—is common in geometry counting problems.

Recommended for interviews: The hash table + enumeration approach is what interviewers expect. A brute force over every quadruple of points is easy to reason about but runs in O(n^4), which is impractical. Enumerating segments and grouping by slope demonstrates strong problem decomposition and efficient use of hashing.

Solution

We can combine all points pairwise, calculate the slope and intercept of the line corresponding to each pair of points, record them using a hash table, and calculate the sum of the number of pairs formed by lines with the same slope but different intercepts. Note that for parallelograms, we will count them twice in the above calculation, so we need to subtract them.

The diagonals of a parallelogram share the same midpoint. Therefore, we also combine all points pairwise, calculate the midpoint coordinates and slope of each pair of points, record them using a hash table, and calculate the sum of the number of pairs formed by point pairs with the same slope and the same midpoint coordinates.

Specifically, we use two hash tables cnt1 and cnt2 to record the following information:

  • cnt1 records the number of occurrences of slope k and intercept b, with the key being the slope k and the value being another hash table that records the number of occurrences of intercept b;
  • cnt2 records the number of occurrences of the midpoint coordinates and slope k of point pairs, with the key being the midpoint coordinates p of the point pair and the value being another hash table that records the number of occurrences of slope k.

For a point pair (x_1, y_1) and (x_2, y_2), we denote dx = x_2 - x_1 and dy = y_2 - y_1. If dx = 0, it means the two points are on the same vertical line, and we denote the slope k = +infty and the intercept b = x_1; otherwise, the slope k = \frac{dy}{dx} and the intercept b = \frac{y_1 cdot dx - x_1 cdot dy}{dx}. The midpoint coordinates p of the point pair can be expressed as p = (x_1 + x_2 + 2000) cdot 4000 + (y_1 + y_2 + 2000), where the offset is added to avoid negative numbers.

Next, we iterate through all point pairs, calculate the corresponding slope k, intercept b, and midpoint coordinates p, and update the hash tables cnt1 and cnt2.

Then, we iterate through the hash table cnt1. For each slope k, we calculate the sum of all pairwise combinations of the occurrence counts of intercept b and add it to the answer. Finally, we iterate through the hash table cnt2. For each midpoint coordinate p, we calculate the sum of all pairwise combinations of the occurrence counts of slope k and subtract it from the answer.

The time complexity is O(n^2) and the space complexity is O(n^2), 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 (Check All Quadruples)O(n^4)O(1)Only for understanding the geometry or very small input sizes
Hash Table + Segment EnumerationO(n^2)O(n^2)General case; groups parallel segments by slope and counts valid pairs efficiently
Slope Grouping with Line SeparationO(n^2)O(n^2)Preferred optimized implementation that avoids counting collinear segments

Video Solution

Count Number of Trapezoids II | Detailed in Simple Words | Leetcode 3625 | codestorywithMIK • codestorywithMIK • 6,209 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Number of Trapezoids II easy or hard?
Count Number of Trapezoids II is considered a Hard problem because it combines geometry, hashing, and combinatorial counting. The main challenge is recognizing that trapezoids can be counted by grouping parallel segments rather than checking every quadruple of points.
Count Number of Trapezoids II Python/Java solution
Most implementations enumerate point pairs and store slope groups in a dictionary (Python) or HashMap (Java). After grouping segments, you iterate through each bucket and count valid segment pairs using combinatorics. The same logic translates easily to C++, Go, and TypeScript.
How to solve Count Number of Trapezoids II in O(n^2)?
Iterate over all pairs of points and compute the normalized slope of each segment. Store segments in a hash map keyed by slope. Within each slope group, separate segments by line intercept and count pairs of segments from different lines. Each such pair represents parallel sides that can form a trapezoid.
What is the best approach for Count Number of Trapezoids II?
The most efficient approach enumerates all point pairs as segments and groups them by slope using a hash table. Parallel segments share the same slope, so each slope bucket contains candidate bases for trapezoids. By separating segments that lie on different lines and counting valid combinations, you can compute the answer in O(n^2) time.
Is Count Number of Trapezoids II asked at Google/Amazon/Meta?
Geometry counting problems involving slopes, hashing, and pair enumeration appear in interviews at large companies such as Google, Amazon, and Meta. Variations of this problem test knowledge of computational geometry and efficient pair aggregation techniques.
What data structure is used in Count Number of Trapezoids II?
A hash table (hash map) is the core data structure. It groups segments by normalized slope so parallel segments can be processed together. Additional structures may store intercepts or counts to avoid counting collinear segments.
What is the time complexity of Count Number of Trapezoids II?
The optimal solution runs in O(n^2) time because every pair of points is processed once to form a segment. Hash table grouping and combination counting are also bounded by the number of segments. Space complexity is O(n^2) in the worst case due to storing slope groups.

Ready to solve this problem?

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

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays