Welcome to Subscribe On Youtube

3623. Count Number of Trapezoids I

Description

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:

• Using points [1,0], [2,0], [3,2], and [2,2].
• Using points [2,0], [3,0], [3,2], and [2,2].
• Using points [1,0], [3,0], [3,2], and [2,2].

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:

• 4 <= points.length <= 105
• –108 <= xi, yi <= 108
• All points are pairwise distinct.

Solutions

Solution 1

• Java
• C++
• Python
• Go
• TypeScript

• class Solution {
      public int countTrapezoids(int[][] points) {
          final int mod = (int) 1e9 + 7;
          Map<Integer, Integer> cnt = new HashMap<>();
          for (var p : points) {
              cnt.merge(p[1], 1, Integer::sum);
          }
          long ans = 0, s = 0;
          for (int v : cnt.values()) {
              long t = 1L * v * (v - 1) / 2;
              ans = (ans + s * t) % mod;
              s += t;
          }
          return (int) ans;
      }
  }
  
  

• class Solution {
  public:
      int countTrapezoids(vector<vector<int>>& points) {
          const int mod = 1e9 + 7;
          unordered_map<int, int> cnt;
          for (auto& p : points) {
              cnt[p[1]]++;
          }
          long long ans = 0, s = 0;
          for (auto& [_, v] : cnt) {
              long long t = 1LL * v * (v - 1) / 2;
              ans = (ans + s * t) % mod;
              s += t;
          }
          return (int) ans;
      }
  };
  
  

• class Solution:
      def countTrapezoids(self, points: List[List[int]]) -> int:
          mod = 10**9 + 7
          cnt = Counter(p[1] for p in points)
          ans = s = 0
          for v in cnt.values():
              t = v * (v - 1) // 2
              ans = (ans + s * t) % mod
              s += t
          return ans
  
  

• func countTrapezoids(points [][]int) int {
  	const mod = 1_000_000_007
  	cnt := make(map[int]int)
  	for _, p := range points {
  		cnt[p[1]]++
  	}
  
  	var ans, s int64
  	for _, v := range cnt {
  		t := int64(v) * int64(v-1) / 2
  		ans = (ans + s*t) % mod
  		s += t
  	}
  	return int(ans)
  }
  
  

• function countTrapezoids(points: number[][]): number {
      const mod = 1_000_000_007;
      const cnt = new Map<number, number>();
  
      for (const p of points) {
          cnt.set(p[1], (cnt.get(p[1]) ?? 0) + 1);
      }
  
      let ans = 0;
      let s = 0;
      for (const v of cnt.values()) {
          const t = (v * (v - 1)) / 2;
          const mul = BigInt(s) * BigInt(t);
          ans = Number((BigInt(ans) + mul) % BigInt(mod));
          s += t;
      }
  
      return ans;
  }
  
  

All Problems

All Solutions