Count Number of Trapezoids I - Video Solutions
Count Number of Trapezoids I | Simplest Explanation | Detailed | Leetcode 3623 | codestorywithMIK
Count Number of Trapezoids I - Video Solution
Watch 10 video solutions for Count Number of Trapezoids I, a medium level problem involving Array, Hash Table, Math. This walkthrough by codestorywithMIK has 7,521 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.
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.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Quadruple Enumeration | O(n^4) | O(1) | Conceptual baseline; useful for verifying small inputs |
| Enumerate All Segments and Check Parallelism | O(n^2) | O(n^2) | General geometry problems where slopes must be compared |
| Hash Map by Y-Level + Segment Pair Enumeration | O(n + k^2) | O(n) | Optimal for horizontal parallel sides; typical interview solution |