Count Number of Trapezoids II - Video Solutions
Count Number of Trapezoids II | Detailed in Simple Words | Leetcode 3625 | codestorywithMIK
Count Number of Trapezoids II - Video Solution
Watch 10 video solutions for Count Number of Trapezoids II, a hard level problem involving Array, Hash Table, Math. This walkthrough by codestorywithMIK has 6,209 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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.
Complexity Analysis
| Approach | Time | Space | When 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 Enumeration | O(n^2) | O(n^2) | General case; groups parallel segments by slope and counts valid pairs efficiently |
| Slope Grouping with Line Separation | O(n^2) | O(n^2) | Preferred optimized implementation that avoids counting collinear segments |