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

countTrapezoids.js

/**
 * @param {number[][]} points
 * @return {number}
 */
var countTrapezoids = function(points) {
    const MOD = 1e9 + 7;

    // Step 1: Group points by y-coordinate
    let yGroups = new Map();
    for (let [x, y] of points) {
        if (!yGroups.has(y)) yGroups.set(y, []);
        yGroups.get(y).push(x);
    }

    // Step 2: Count pairs per level
    let pairs = [];
    for (let xs of yGroups.values()) {
        let n = xs.length;
        if (n >= 2) {
            pairs.push((n * (n - 1)) / 2);
        }
    }

    // Step 3: Use formula to avoid O(m^2)
    let sum = 0n, sumSq = 0n;
    for (let p of pairs) {
        let bigP = BigInt(p);
        sum += bigP;
        sumSq += bigP * bigP;
    }

    let total = (sum * sum - sumSq) / 2n;
    total = total % BigInt(MOD);

    return Number(total);
};