3623. Count Number of Trapezoids I

T: O(n + k), n is the number of points, k is the number of segments

S: O(k)

class Solution {
    private static final int MOD = 1_000_000_007;

    public int countTrapezoids(int[][] points) {
        Map<Integer, Integer> yToCount = new HashMap<>();
        for (int[] point : points) {
            int y = point[1];
            yToCount.put(y, yToCount.getOrDefault(y, 0) + 1);
        }

        // Step 1: Build a list of horizontal segment counts (C(n, 2)) for each y-level
        List<Long> segments = new ArrayList<>();
        for (int count : yToCount.values()) {
            if (count >= 2) {
                long seg = (long) count * (count - 1) / 2;
                segments.add(seg % MOD);
            }
        }

        // Step 2: Build suffix sum array
        int k = segments.size();
        long[] suffixSum = new long[k+1]; // suffixSum[i] = sum of segments[i..end]
        for (int i = k - 1; i >= 0; i--) {
            suffixSum[i] = (segments.get(i) + suffixSum[i + 1]) % MOD;
        }

        // Step 3: Compute result with prefix-sum trick (count each pair once)
        long result = 0;
        for (int i = 0; i < k - 1; i++) {
            result = (result + segments.get(i) * suffixSum[i + 1] % MOD) % MOD;
        }

        return (int) result;
    }
}


/**

2 3 3 

sufixsum -> can replace nested pair loop!! magically!

1 2 2 0 segment[]
5 4 2.  sufixsum[]

1*4 + 2*2 = 8 equals to nested loop 1*2 + 1*2 + 2*2 = 8

why sufixsum works? because it sum up the nested loop target!
1*4 = 1*2 + 1*2
-> these 2 + 2 sum up first!

1 2 2
1*2 + 1*2 -> actually means 1 * (2+2)
2*2 -> 2 * 2 
so we can use segments[i] * sufixsum[i+1] to replace nested loop caculation!


A horizontal trapezoid is a convex quadrilateral with at least one pair of horizontal sides
-> parallel to the x-axis

find line parallel to the x-axis, Group the points by their y‑coordinate.

Map<y, List<x>> ex: 2,2)  4,2) -> a line paparallel to the x-axis
     ---
---

---

            ----

n*(n-1)/2


[[-73,-72], [64,-72],,[-92,30], [-35,30],[-57,-89],[-19,-89],,]
[-1,-56]


-----30

.......-72

----- -89
 */