LeetCode in Kotlin

3623. Count Number of Trapezoids I

Medium

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 109 + 7.

Example 1:

Input: points = [[1,0],[2,0],[3,0],[2,2],[3,2]]

Output: 3

Explanation:

There are three distinct ways to pick four points that form a horizontal trapezoid:

Example 2:

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

Output: 1

Explanation:

There is only one horizontal trapezoid that can be formed.

Constraints:

Solution

class Solution {
    fun countTrapezoids(points: Array<IntArray>): Int {
        val mod = 1000000007
        val inv = 500000004L
        val map: MutableMap<Int, Int> = HashMap<Int, Int>(points.size)
        for (p in points) {
            map.merge(p[1], 1) { a: Int, b: Int -> Integer.sum(a, b) }
        }
        var sum = 0L
        var sumPairs = 0L
        for (num in map.values) {
            if (num > 1) {
                val pairs = (num.toLong() * (num - 1) / 2) % mod
                sum = (sum + pairs) % mod
                sumPairs = (sumPairs + pairs * pairs % mod) % mod
            }
        }
        var res = (sum * sum % mod - sumPairs + mod) % mod
        res = (res * inv) % mod
        return res.toInt()
    }
}