Count number of trapezoids i

Array Hash Table Math Geometry

48.0% acceptance

Feb 25, 2026

393

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 10^9 + 7.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn count_trapezoids(points: Vec<Vec<i32>>) -> i32 {
    use std::collections::HashMap;
    const MOD: i64 = 1_000_000_007;
    // Group points by y-coordinate
    let mut by_y: HashMap<i32, i64> = HashMap::new();
    for p in &points {
      *by_y.entry(p[1]).or_insert(0) += 1;
    }
    // Total ways to pick 2 parallel horizontal pairs: pairs of y-levels (y1, y2)
    // For each pair (y1, y2), number of ways = C(cnt[y1], 2) * C(cnt[y2], 2) is a rectangle
    // Actually horizontal trapezoids: choose 2 y-levels, pick >= 2 from each
    // But trapezoid needs exactly one pair of parallel sides (not a parallelogram/rectangle)
    // Wait - a horizontal trapezoid is *at least* one pair of horizontal parallel sides.
    // So we count: for each pair of distinct y-values (y1, y2), pick 2 points from row y1
    // and 2 points from row y2 = C(c1,2) * C(c2,2). The 4 points form a horizontal trapezoid
    // as long as they form a convex quadrilateral.
    // For points to be a convex quadrilateral, the x-intervals on the two rows must "overlap"
    // in a specific way. Actually for distinct x values on each row, any pair forms a valid trapezoid.
    // Simpler: count all quadruples with 2 from one y and 2 from another y (no collinearity issue since y differs)
    // = (sum over pairs of y-values) C(c1,2) * C(c2,2)
    // But we need to handle the case where all 4 are collinear (impossible since different y).
    // Also rectangles (parallelograms with horizontal sides) count as trapezoids since they have parallel sides.
    // So answer = sum_{y1 < y2} C(count[y1], 2) * C(count[y2], 2)
    let comb2 = |c: i64| c * (c - 1) / 2 % MOD;
    let vals: Vec<i64> = by_y.values().map(|&c| comb2(c)).collect();
    // sum_{i < j} vals[i] * vals[j]
    let mut result = 0i64;
    let mut prefix_sum = 0i64;
    for &v in &vals {
      result = (result + prefix_sum * v) % MOD;
      prefix_sum = (prefix_sum + v) % MOD;
    }
    result as i32
  }
}