Limited Time Offer:Up to 25% off Hello Interview Premium

Your Dashboard

Interview Coaching

Mock Interviews

1:1 Mentorship

Salary Negotiation

Practice

Learn

System Design

ML System Design

Low Level Design

Code

Behavioral

Salary Negotiation

Interview Guides

Blog

Community

Interview Questions

Interview Experiences

Peer System Design Library

Ask The Community

Discord

Refer a Friend

Pricing

Become a Coach

⌘K

Pricing Become a Coach

⌘K

Tutor

Get Premium

Leetcode 3625. Count Number of Trapezoids II

Count the number of 4-point subsets that form a trapezoid — i.e., a convex quadrilateral with at least one pair of parallel sides — from up to 500 distinct points. The core challenge is combinatorially counting pairs of disjoint point-segments with the same slope (parallel sides) while excluding degenerate/overlapping cases, typically done by grouping point-pairs by reduced slope in O(n^2) time.

DESCRIPTION

Count the number of 4-point subsets that form a trapezoid — i.e., a convex quadrilateral with at least one pair of parallel sides — from up to 500 distinct points.
The core challenge is combinatorially counting pairs of disjoint point-segments with the same slope (parallel sides) while excluding degenerate/overlapping cases, typically done by grouping point-pairs by reduced slope in O(n^2) time.

Input:

points = [[0,0], [1,0], [0,1], [1,1]]

Output:

Explanation: The 4 points form a square, which is a trapezoid (both pairs of opposite sides are parallel). This is the only 4-point subset, so count is 1.

Constraints:

4 <= points.length <= 500
points[i].length == 2
-10^9 <= points[i][0], points[i][1] <= 10^9
All points are distinct (no duplicates)
The answer will fit in a 32-bit integer

Understanding the Problem

Let's understand what we're being asked to do. We have up to 500 distinct points in a 2D plane, and we need to count how many 4-point subsets form a trapezoid - a convex quadrilateral with at least one pair of parallel sides.

For example, given points [[0,0], [1,0], [0,1], [1,1]] (forming a square), we can select all 4 points to form a trapezoid (actually a special trapezoid where both pairs of opposite sides are parallel).

Important constraint: The points must form a convex quadrilateral (no point inside the shape formed by the other three), and we need at least one pair of parallel sides. Two line segments are parallel if they have the same slope.

Key challenge: With 500 points, there are C(500,4) ≈ 2.6 billion possible 4-point subsets. We can't check each one individually! We need to group point-pairs by their slope and count valid combinations.

Edge cases to consider: What if three or more points are collinear (on the same line)? These don't form valid trapezoids. What if two point-pairs overlap (share a point)? We need disjoint pairs for valid trapezoids.

Brute Force Approach

The brute-force approach enumerates all possible 4-point subsets using four nested loops, checking each combination to see if it forms a valid trapezoid. For each subset, we compute slopes of all six possible line segments, check if at least one pair of opposite sides is parallel (same slope), and verify the quadrilateral is convex (no point inside the triangle formed by the other three). This approach is straightforward but extremely inefficient with O(n^4) time complexity, making it impractical for 500 points.

def count_trapezoids(points):
    """
    Brute force approach: Check all 4-point combinations to count trapezoids.
    A trapezoid has at least one pair of parallel sides (same slope).
    Time: O(n^4), Space: O(1)
    """
    n = len(points)
    count = 0
    
    # Try all combinations of 4 points
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                for m in range(k + 1, n):
                    # Get the 4 points
                    p1, p2, p3, p4 = points[i], points[j], points[k], points[m]
                    
                    # Check if these 4 points form a trapezoid
                    if is_trapezoid(p1, p2, p3, p4):
                        count += 1
    
    return count
def is_trapezoid(p1, p2, p3, p4):
    """
    Check if 4 points form a trapezoid.
    Must have at least one pair of parallel sides and be convex.
    """
    # Calculate all 6 possible line segment slopes
    # Sides: (p1,p2), (p2,p3), (p3,p4), (p4,p1)
    # Diagonals: (p1,p3), (p2,p4)
    
    slopes = []
    pairs = [(p1, p2), (p2, p3), (p3, p4), (p4, p1), (p1, p3), (p2, p4)]
    
    for pt1, pt2 in pairs:
        slope = get_slope(pt1, pt2)
        slopes.append(slope)
    
    # Check if opposite sides are parallel (trapezoid condition)
    # Sides: 0=(p1,p2), 1=(p2,p3), 2=(p3,p4), 3=(p4,p1)
    side1_parallel_side3 = slopes[0] == slopes[2]  # (p1,p2) || (p3,p4)
    side2_parallel_side4 = slopes[1] == slopes[3]  # (p2,p3) || (p4,p1)
    
    has_parallel_sides = side1_parallel_side3 or side2_parallel_side4
    
    if not has_parallel_sides:
        return False
    
    # Check convexity: no point should be inside triangle formed by other 3
    if not is_convex_quad(p1, p2, p3, p4):
        return False
    
    return True
def get_slope(p1, p2):
    """
    Calculate slope between two points.
    Returns tuple (dy, dx) in reduced form to handle vertical lines.
    """
    dx = p2[0] - p1[0]
    dy = p2[1] - p1[1]
    
    if dx == 0:
        return (1, 0)  # Vertical line
    if dy == 0:
        return (0, 1)  # Horizontal line
    
    # Reduce to lowest terms using GCD
    from math import gcd
    g = gcd(abs(dy), abs(dx))
    dy, dx = dy // g, dx // g
    
    # Normalize sign
    if dx < 0:
        dy, dx = -dy, -dx
    
    return (dy, dx)
def is_convex_quad(p1, p2, p3, p4):
    """
    Check if quadrilateral is convex using cross products.
    All cross products should have the same sign.
    """
    def cross_product_sign(a, b, c):
        # Cross product of vectors (b-a) and (c-b)
        return (b[0] - a[0]) * (c[1] - b[1]) - (b[1] - a[1]) * (c[0] - b[0])
    
    # Check all 4 vertices
    signs = []
    vertices = [p1, p2, p3, p4]
    
    for i in range(4):
        a = vertices[i]
        b = vertices[(i + 1) % 4]
        c = vertices[(i + 2) % 4]
        cp = cross_product_sign(a, b, c)
        signs.append(cp)
    
    # All cross products should have same sign (all positive or all negative)
    all_positive = all(s > 0 for s in signs)
    all_negative = all(s < 0 for s in signs)
    
    return all_positive or all_negative

Start trapezoid counting with brute force

0 / 24

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n^4) Four nested loops to enumerate all C(n,4) combinations of 4 points, with constant work per combination to check trapezoid validity

Space Complexity: O(1) Only constant extra space needed for slope calculations and validity checks

Building Intuition

A trapezoid requires at least one pair of parallel sides. Two line segments are parallel if they connect points with the same slope.

If we group all point-pairs by their slope (in reduced form like dy/dx), then any two pairs from the same slope group are parallel! The key is finding pairs of disjoint point-pairs (no shared points) with the same slope.

Instead of checking all C(n,4) combinations of 4 points (which would be O(n^4)), we can:

Compute slopes for all O(n^2) point-pairs
Group pairs by slope
For each slope group, count combinations of disjoint pairs

This transforms a brute-force O(n^4) problem into an O(n^2) grouping problem with efficient counting.

Think of organizing point-pairs into buckets by their slope:

Bucket for slope 0 (horizontal): all horizontal segments
Bucket for slope 1: all segments with 45° angle
Bucket for slope ∞ (vertical): all vertical segments
etc.

Within each bucket, if we pick any two segments that don't share a point, we have a pair of parallel sides! Now we just need to verify the 4 points form a convex quadrilateral (not degenerate/overlapping).

The challenge is efficiently counting valid combinations within each slope bucket while excluding overlapping pairs.

Common Mistakes

Using floating-point arithmetic for slopes leads to precision errors - use reduced fractions (dy/dx with GCD) or integer ratios instead

Forgetting to check for disjoint pairs - two point-pairs that share a point cannot form a valid trapezoid

Not handling vertical lines (infinite slope) as a special case - use a sentinel value or separate handling

Counting degenerate cases where three or more points are collinear - these don't form valid convex quadrilaterals

Off-by-one errors in combinatorial counting - when counting pairs from a group, use C(n,2) = n*(n-1)/2 formula carefully

Optimal Solution

The optimal approach groups all point-pairs by their slope (reduced to lowest terms to handle precision). For each slope group, we count combinations of disjoint point-pairs (pairs that don't share any points). Two disjoint pairs with the same slope form parallel sides of a potential trapezoid. We iterate through all O(n^2) point-pairs once, hash them by slope, then for each slope group, count valid disjoint pair combinations while excluding degenerate cases (collinear points, overlapping segments). This reduces the problem from O(n^4) enumeration to O(n^2) grouping with efficient counting.

from math import gcd
from collections import defaultdict
def count_trapezoids(points):
    """
    Count trapezoids formed by 4-point subsets with at least one pair of parallel sides.
    Uses slope grouping to find parallel segments in O(n^2) time.
    """
    n = len(points)
    if n < 4:
        return 0
    
    # Group point-pairs by slope (reduced to lowest terms)
    slope_groups = defaultdict(list)
    
    # Generate all point-pairs and group by slope
    for i in range(n):
        for j in range(i + 1, n):
            x1, y1 = points[i]
            x2, y2 = points[j]
            
            # Calculate slope as reduced fraction (dy, dx)
            dx = x2 - x1
            dy = y2 - y1
            
            # Reduce to lowest terms
            if dx == 0:
                slope = (1, 0)  # Vertical line
            elif dy == 0:
                slope = (0, 1)  # Horizontal line
            else:
                g = gcd(abs(dx), abs(dy))
                dx //= g
                dy //= g
                # Normalize sign: make dx positive
                if dx < 0:
                    dx, dy = -dx, -dy
                slope = (dy, dx)
            
            # Store pair with its slope
            slope_groups[slope].append((i, j))
    
    trapezoid_count = 0
    
    # For each slope group, count disjoint pairs
    for slope, pairs in slope_groups.items():
        m = len(pairs)
        
        # Count combinations of disjoint pairs
        for p1 in range(m):
            i1, j1 = pairs[p1]
            
            for p2 in range(p1 + 1, m):
                i2, j2 = pairs[p2]
                
                # Check if pairs are disjoint (no shared points)
                if i1 != i2 and i1 != j2 and j1 != i2 and j1 != j2:
                    # Check not collinear (all 4 points)
                    x1, y1 = points[i1]
                    x2, y2 = points[j1]
                    x3, y3 = points[i2]
                    x4, y4 = points[j2]
                    
                    # Use cross product to check collinearity
                    # Points are collinear if area of triangle is 0
                    area1 = abs((x2 - x1) * (y3 - y1) - (y2 - y1) * (x3 - x1))
                    area2 = abs((x2 - x1) * (y4 - y1) - (y2 - y1) * (x4 - x1))
                    
                    if area1 > 0 and area2 > 0:
                        trapezoid_count += 1
    
    return trapezoid_count

Initialize trapezoid counting with geometry visualization

0 / 84

Test Your Knowledge

Complexity Analysis

Time Complexity: O(n^2) Computing slopes for all point-pairs takes O(n^2). For each slope group, counting disjoint pairs is proportional to the group size, which sums to O(n^2) across all groups.

Space Complexity: O(n^2) Storing all point-pairs grouped by slope requires O(n^2) space in the worst case where all pairs have different slopes

What We've Learned

Slope-based grouping with GCD normalization: When counting geometric relationships involving parallel lines, group point-pairs by their reduced slope (dy/dx after dividing by GCD) as a hashmap key. This transforms an O(n⁴) brute-force trapezoid check into O(n²) by pre-computing all parallel segment pairs, enabling efficient counting of combinations.
Combinatorial counting over enumeration: Instead of enumerating all 4-point subsets (O(n⁴)), count trapezoids by iterating through pairs of parallel segments and using C(k,2) = k*(k-1)/2 to count valid trapezoids formed by k parallel segments with the same slope. This reduces complexity dramatically when many point-pairs share the same slope.
Disjoint segment validation: The critical implementation detail is ensuring the two parallel sides share no common points - use set operations or coordinate checks to verify that segments (p1,p2) and (p3,p4) have no overlap before counting them as a valid trapezoid, preventing degenerate cases where points coincide.
Vertical slope edge case: Always handle vertical lines separately (dx=0) since division by zero breaks slope calculations. Store vertical segments with a special key like (infinity, x-coordinate) or use a separate data structure, as this is a common source of runtime errors in geometry problems.
Hash key design for geometric properties: Use tuple keys of (normalized_dy, normalized_dx) rather than floating-point slope values to avoid precision errors. Integer-based keys with GCD reduction ensure exact equality checks and prevent hash collisions from floating-point rounding, crucial for correctness in computational geometry.
Pattern applies to collinearity and parallelism problems: This slope-grouping technique extends to any problem requiring detection of parallel segments, collinear points, or angle-based relationships - think of it whenever you need to find geometric patterns across multiple point combinations (convex hulls, line intersections, polygon detection).

Test Your Understanding

Why is geometry the right data structure for this problem?

geometry provides the optimal access pattern

It's the only data structure that works

It's the easiest to implement

It uses the least memory

Select an answer to see the explanation

Question Timeline

See when this question was last asked and where, including any notes left by other candidates.

Company

Level

Region

Comments

Your account is free and you can post anonymously if you choose.

Hello Interview Premium

Recent interview questions

System Design Guided Practice

Exclusive content

Learn More

Leetcode 3625. Count Number of Trapezoids II

DESCRIPTION

Understanding the Problem

Brute Force Approach

Test Your Knowledge

Complexity Analysis

Building Intuition

Common Mistakes

Optimal Solution

Test Your Knowledge

Complexity Analysis

What We've Learned

Related Concepts and Problems to Practice

Test Your Understanding

Question Timeline

Comments

Questions

Learn

Links

Legal

Contact