#3623

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Count Number of Trapezoids I

Given a list of distinct points, count the number of unique horizontal trapezoids that can be formed by selecting four points.

array hash table math geometry

Problem Statement

You are given a 2D integer array points, where each point is represented as [xi, yi] on the Cartesian plane. A horizontal trapezoid is a convex quadrilateral that has at least one pair of sides parallel to the x-axis. This means that the selected points must have the same y-coordinate for the parallel sides.

Your task is to return the number of distinct horizontal trapezoids that can be formed by selecting four points from the array, with the constraint that all points are pairwise distinct.

Examples

Example 1

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

Output: 3

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

Example 2

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

Output: 1

There is only one horizontal trapezoid that can be formed.

Constraints

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

Solution Approach

Scan the points and categorize by y-coordinate

To efficiently count horizontal trapezoids, scan through the array of points, grouping the points by their y-coordinate. This allows easy identification of potential pairs of parallel lines.

Use hash table to track frequency

Implement a hash table to store the frequency of each y-coordinate. By doing so, it becomes easier to calculate how many points lie on a line parallel to the x-axis, which helps to form the parallel sides of the trapezoid.

Count valid trapezoids based on conditions

Once the points are categorized and stored, count the number of ways to select four points with the same y-coordinate to form the two horizontal sides of a trapezoid. Carefully check the geometric conditions for a valid trapezoid formation.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

The time complexity depends on the hash table operations, which in the worst case are O(n) for scanning the points and O(1) for each insertion or lookup. The space complexity is O(n) due to the need to store the points and hash table entries.

What Interviewers Usually Probe

Candidate demonstrates understanding of geometric properties like parallel lines.
Candidate efficiently uses hash tables to track and group points.
Candidate is able to optimize their approach to handle the input size constraint.

Common Pitfalls or Variants

Common pitfalls

Misunderstanding the concept of parallel lines, leading to incorrect trapezoid formation.
Failure to account for all distinct point combinations.
Not optimizing the approach to handle larger inputs within time limits.

Follow-up variants

Implementing the solution in a higher-dimensional space.
Extending the solution to count trapezoids with vertical sides as well.
Exploring alternative approaches like sorting or dynamic programming.

FAQ

How do I count the number of horizontal trapezoids efficiently?

Efficiently count trapezoids by scanning through the points and grouping them by their y-coordinate using a hash table. Then, calculate the possible trapezoids from those groups.

What is the primary pattern in this problem?

The primary pattern is array scanning plus hash lookup, which helps categorize points by their y-coordinate to identify potential trapezoids.

Can the approach handle large input sizes?

Yes, the approach is designed to handle inputs up to 10^5 points efficiently by utilizing hash tables for fast lookups.

What role does the y-coordinate play in forming a trapezoid?

The y-coordinate determines which points can form the horizontal sides of the trapezoid, as these sides must be parallel to the x-axis.

How do I optimize the solution for this problem?

Optimize by categorizing points by y-coordinate using a hash table, which enables fast lookups and efficient counting of potential trapezoids.

terminal

Solution

Solution 1: Enumeration

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.

1

2

3

4

5

6

7

8

9

10

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        mod = 10**9 + 7
        cnt = Counter(p[1] for p in points)
        ans = s = 0
        for v in cnt.values():
            t = v * (v - 1) // 2
            ans = (ans + s * t) % mod
            s += t
        return ans

Continue Practicing

#3625 count number of trapezoids ii #3588 find maximum area of a triangle #3591 check if any element has prime frequency