Created
December 2, 2025 17:38
-
-
Save tatsuyax25/5516d0c2983069e037eaa8071d1e5b8f to your computer and use it in GitHub Desktop.
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
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| /** | |
| * @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); | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment