2025-12-02 Daily Challenge

Posted on:
Posted modified:
In: DailyChallenge

Today I have done leetcode's December LeetCoding Challenge with cpp.

December LeetCoding Challenge 2

Description

Count Number of Trapezoids I

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.

Solution

class Solution {
  const int MOD = 1e9 + 7;
public:
  int countTrapezoids(vector<vector<int>>& points) {
    map<int, long long> pointsOnSameXAxis;
    for(const auto &p : points) {
      pointsOnSameXAxis[p[1]] += 1;
    }
    long long sum = 0;
    for(auto &[x, c] : pointsOnSameXAxis) {
      c = c * (c - 1) / 2;
      sum += c;
      sum %= MOD;
    }

    long long answer = 0;
    for(const auto &[x, c] : pointsOnSameXAxis) {
      answer += 1LL * (sum - c + MOD) % MOD * c % MOD;
      answer %= MOD;
    }
    return 1LL * answer * 500000004 % MOD;
  }
};

// Accepted
// 554/554 cases passed (113 ms)
// Your runtime beats 30.36 % of cpp submissions
// Your memory usage beats 60.22 % of cpp submissions (193.7 MB)
Algorithm