leetcode

commit 1b31903ae86ec589edcae1256a934211c1d02692
parent 7792bb7d4ecaf9449b7a3c88936af32816eb881a
Author: Jack Sangdahl <jack@pngu.org>
Date:   Tue,  2 Dec 2025 09:07:35 +0100

3623. count number of trapezoids 1

Diffstat:
A
count_num_trapezoid_1.c
 | 
124
+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A
count_num_trapezoid_1.py
 | 
35
+++++++++++++++++++++++++++++++++++

2 files changed, 159 insertions(+), 0 deletions(-)
diff --git a/count_num_trapezoid_1.c b/count_num_trapezoid_1.c
@@ -0,0 +1,124 @@
+// 3623. Count Number of Trapezoids I
+#include "leetcode.h"
+
+/*
+ * you are given a 2d integer array 'points' where 'points[i] = [x_i, y_i]'
+ * represents the coordinates of the i'th point on the cartesian plane. a
+ * horizontal trapezoid is a convex quadrilateral with at least one pair of
+ * horizontal sides. 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 very
+ * large, return it modulo 1e9 + 7.
+ */
+
+struct hash_node {
+  int key;
+  long long val;
+  struct hash_node *next;
+};
+
+struct hash_map {
+  struct hash_node **buckets;
+  int size;
+};
+
+struct hash_map *hash_map_init(int size) {
+  struct hash_map *obj = (struct hash_map *)malloc(sizeof(struct hash_map));
+  obj->size = size;
+  obj->buckets = (struct hash_node **)calloc(size, sizeof(struct hash_node *));
+  return obj;
+}
+
+int hash_func(int key, int size) { return abs(key) % size; }
+
+void put(struct hash_map *obj, int key, long long val) {
+  int idx = hash_func(key, obj->size);
+  struct hash_node *curr = obj->buckets[idx];
+  while (curr) {
+    if (curr->key == key) {
+      curr->val = val;
+      return;
+    }
+    curr = curr->next;
+  }
+  struct hash_node *new = (struct hash_node *)malloc(sizeof(struct hash_node));
+  new->key = key;
+  new->val = val;
+  new->next = obj->buckets[idx];
+  obj->buckets[idx] = new;
+}
+
+long long get(struct hash_map *obj, int key) {
+  int idx = hash_func(key, obj->size);
+  struct hash_node *curr = obj->buckets[idx];
+  while (curr) {
+    if (curr->key == key)
+      return curr->val;
+    curr = curr->next;
+  }
+  return 0;
+}
+
+void increment(struct hash_map *obj, int key) {
+  int idx = hash_func(key, obj->size);
+  struct hash_node *curr = obj->buckets[idx];
+  while (curr) {
+    if (curr->key == key) {
+      curr->val++;
+      return;
+    }
+    curr = curr->next;
+  }
+  struct hash_node *new = (struct hash_node *)malloc(sizeof(struct hash_node));
+  new->key = key;
+  new->val = 1;
+  new->next = obj->buckets[idx];
+  obj->buckets[idx] = new;
+}
+
+void hash_map_free(struct hash_map *obj) {
+  for (int i = 0; i < obj->size; i++) {
+    struct hash_node *curr = obj->buckets[i];
+    while (curr) {
+      struct hash_node *tmp = curr;
+      curr = curr->next;
+      free(tmp);
+    }
+  }
+  free(obj->buckets);
+  free(obj);
+}
+
+int countTrapezoids(int **points, int pointsSize, int *pointsColSize) {
+  static int mod = 1e9 + 7;
+  struct hash_map *groups = hash_map_init(pointsSize * 2);
+  for (int i = 0; i < pointsSize; i++)
+    increment(groups, points[i][1]);
+  long long ans = 0, total = 0;
+  for (int i = 0; i < groups->size; i++) {
+    struct hash_node *curr = groups->buckets[i];
+    while (curr) {
+      long long cnt = curr->val, lines = cnt * (cnt - 1) / 2;
+      ans = (ans + total * lines) % mod;
+      total = (total + lines) % mod;
+      curr = curr->next;
+    }
+  }
+  hash_map_free(groups);
+  return (int)ans;
+}
+
+int main() {
+  int p1i[5][2] = {{1, 0}, {2, 0}, {3, 0}, {2, 2}, {3, 2}};
+  int p2i[4][2] = {{0, 0}, {1, 0}, {0, 1}, {2, 1}};
+  struct two_d_arr *p1 =
+      two_d_arr_init(ARRAY_SIZE(p1i), ARRAY_SIZE(p1i[0]), p1i);
+  struct two_d_arr *p2 =
+      two_d_arr_init(ARRAY_SIZE(p2i), ARRAY_SIZE(p2i[0]), p2i);
+  printf("%d\n",
+         countTrapezoids(p1->arr, p1->row_size, p1->col_size)); // expect: 3
+  printf("%d\n",
+         countTrapezoids(p2->arr, p2->row_size, p2->col_size)); // expect: 1
+  two_d_arr_free(p1);
+  two_d_arr_free(p2);
+}
diff --git a/count_num_trapezoid_1.py b/count_num_trapezoid_1.py
@@ -0,0 +1,35 @@
+# 3623. Count Number of Trapezoids I
+from collections import defaultdict
+
+"""
+you are given a 2d integer array 'points' where 'points[i] = [x_i, y_i]'
+represents the coordinates of the i'th point on the cartesian plane. a
+horizontal trapezoid is a convex quadrilateral with at least one pair of
+horizontal sides. 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 very
+large, return it modulo 1e9 + 7.
+"""
+
+
+class Solution(object):
+    def countTrapezoids(self, points):
+        """
+        :type points: List[List[int]]
+        :rtype: int
+        """
+        groups, mod = defaultdict(int), 10**9 + 7
+        for _, y in points:
+            groups[y] += 1
+        ans, total = 0, 0
+        for y, cnt in groups.items():
+            lines = cnt * (cnt - 1) // 2
+            ans = (ans + total * lines) % mod
+            total = (total + lines) % mod
+        return ans
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.countTrapezoids(points=[[1, 0], [2, 0], [3, 0], [2, 2], [3, 2]]))
+    print(obj.countTrapezoids(points=[[0, 0], [1, 0], [0, 1], [2, 1]]))