LeetCode 3625 - Count Number of Trapezoids II

The problem asks us to count the number of unique trapezoids that can be formed from a set of points on a 2D Cartesian plane. Each point is given as a pair of integers representing its x and y coordinates.

leetcodehardarrayhash-tablemathgeometry

LeetCode Problem 3625

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Math, Geometry

Solution

Problem Understanding

The problem asks us to count the number of unique trapezoids that can be formed from a set of points on a 2D Cartesian plane. Each point is given as a pair of integers representing its x and y coordinates. A trapezoid is defined as a convex quadrilateral with at least one pair of parallel sides. In mathematical terms, two sides are parallel if their slopes are equal.

The input is a list of points, and the output is a single integer representing the total number of distinct sets of four points that form a trapezoid. The constraints are important because they indicate the problem's scale: we have between 4 and 500 points, and each coordinate ranges from -1000 to 1000. All points are guaranteed to be distinct, which means we do not need to handle duplicates.

Edge cases to consider include points that are collinear (which cannot form trapezoids), sets of points that form rectangles (which are also trapezoids since a rectangle has parallel sides), and minimal inputs with exactly four points.

Approaches

The brute-force approach involves iterating over all possible combinations of four points and checking whether the quadrilateral formed has at least one pair of parallel sides. This requires checking the slopes of all six possible pairs of sides for each combination. While this method is straightforward and guarantees correctness, it is extremely slow because the number of combinations grows as $O(n^4)$, which is infeasible for $n = 500$.

The key insight for an optimal solution is to leverage geometry and hash maps. Instead of checking every set of four points individually, we can consider pairs of points as defining potential lines and group them by their slope. Two lines with the same slope can serve as the parallel sides of a trapezoid. By using a hash map keyed on the slope, we can efficiently count how many line pairs share the same slope and compute the number of trapezoids combinatorially.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^4) O(1) Check all quadruples of points, compute slopes, and verify parallelism
Optimal O(n^2) O(n^2) Group line segments by slope using hash maps, count pairs combinatorially

Algorithm Walkthrough

  1. Initialize a hash map slope_map to group line segments by their slope. Each key is a slope expressed as a fraction (dy, dx) reduced to its simplest form to handle floating-point issues.
  2. Iterate over all pairs of points (p1, p2). For each pair, compute the slope as (y2 - y1, x2 - x1), and normalize it by dividing by their greatest common divisor. If dx is zero, treat it as a vertical line.
  3. Store the pair of points in slope_map[slope]. This allows us to efficiently find all pairs of points that lie on lines with the same slope.
  4. After grouping all line segments by slope, iterate over each slope group. For each group with at least two line segments, compute the number of unique trapezoids that can be formed. If a slope group has k lines, the number of trapezoids is C(k, 2), because any two lines from this group can serve as the parallel sides.
  5. Sum the counts across all slope groups. This gives the total number of trapezoids.

Why it works: By grouping line segments by slope, we guarantee that every counted pair has parallel sides. We ensure uniqueness because each line segment pair is considered combinatorially, and every trapezoid requires exactly two lines with the same slope.

Python Solution

from typing import List
from math import gcd
from collections import defaultdict

class Solution:
    def countTrapezoids(self, points: List[List[int]]) -> int:
        slope_map = defaultdict(list)
        n = len(points)
        
        # Step 1: Group all line segments by slope
        for i in range(n):
            for j in range(i + 1, n):
                x1, y1 = points[i]
                x2, y2 = points[j]
                dy = y2 - y1
                dx = x2 - x1
                g = gcd(dy, dx)
                if g != 0:
                    dy //= g
                    dx //= g
                # Normalize slope direction
                if dx < 0:
                    dy, dx = -dy, -dx
                elif dx == 0 and dy < 0:
                    dy = -dy
                slope_map[(dy, dx)].append((i, j))
        
        # Step 2: Count trapezoids
        result = 0
        for pairs in slope_map.values():
            k = len(pairs)
            if k > 1:
                result += k * (k - 1) // 2  # C(k, 2)
        
        return result

The Python code first computes slopes and normalizes them to handle vertical and negative lines consistently. It then stores each segment in a hash map keyed by the slope. Finally, it counts combinations of line segments with the same slope to find the total number of trapezoids. The gcd ensures slopes are reduced to their simplest form, preventing floating-point errors.

Go Solution

package main

import (
    "fmt"
)

func gcd(a, b int) int {
    if b == 0 {
        return a
    }
    return gcd(b, a%b)
}

func countTrapezoids(points [][]int) int {
    n := len(points)
    slopeMap := make(map[[2]int][][2]int)
    
    // Step 1: Group all line segments by slope
    for i := 0; i < n; i++ {
        for j := i + 1; j < n; j++ {
            x1, y1 := points[i][0], points[i][1]
            x2, y2 := points[j][0], points[j][1]
            dy, dx := y2-y1, x2-x1
            g := gcd(dy, dx)
            if g != 0 {
                dy /= g
                dx /= g
            }
            if dx < 0 {
                dy, dx = -dy, -dx
            } else if dx == 0 && dy < 0 {
                dy = -dy
            }
            slope := [2]int{dy, dx}
            slopeMap[slope] = append(slopeMap[slope], [2]int{i, j})
        }
    }
    
    // Step 2: Count trapezoids
    result := 0
    for _, pairs := range slopeMap {
        k := len(pairs)
        if k > 1 {
            result += k * (k - 1) / 2
        }
    }
    
    return result
}

In Go, we use arrays [2]int as hash map keys for slope pairs. We also define a gcd helper function to reduce the slope fraction. The overall logic mirrors the Python solution, handling normalization for vertical and negative slopes carefully.

Worked Examples

Example 1: points = [[-3,2],[3,0],[2,3],[3,2],[2,-3]]

Compute all pairs and group by slope:

Pair Slope Group
(-3,2),(2,3) 1/5 slope1
(-3,2),(3,0) -1/3 slope2
(-3,2),(3,2) 0/1 slope3
... ... ...

After grouping, we have two groups of lines that can form trapezoids. Counting pairs in each group gives the result 2.

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

Slope groups:

Pair Slope Group
(0,0),(1,0) 0/1 horizontal
(0,1),(2,1) 0/1 horizontal

There is one pair of lines with the same slope, producing 1 trapezoid.

Complexity Analysis

Measure Complexity Explanation
Time O(n^2) We iterate over all pairs of points to compute slopes and store in hash map
Space O(n^2) Storing all line segments in a hash map keyed by slope

The algorithm avoids O(n^4) brute-force enumeration by grouping lines and using combinatorial counting. Space complexity is quadratic because we store all line segments.

Test Cases

# Provided examples
assert Solution().countTrapezoids([[-3,2],[3,0],[2,3],[3,2],[2,-3]]) == 2  # multiple trapezoids
assert Solution().countTrapezoids([[0,0],[1,0],[0,1],[2,1]]) == 1  # one trapezoid

# Minimal input
assert Solution().countTrapezoids([[0,0],[0,1],[1,0],[1,1]]) == 2  # rectangle counts as 2 trapezoids with either pair of parallel sides

# No trapezoid possible
assert Solution().countTrapezoids([[0,0],[1,1],[2,2],[3,3]]) == 0  # collinear points

# Large input
points