leetcode

commit 3a720b8d362062dae908f98a96c0a183af100fad
parent 6755614b862ad4b6c914194d061fdef9e6646d6c
Author: Jack Sangdahl <jack@pngu.org>
Date:   Wed, 10 Dec 2025 09:25:27 +0100

3583. count special triplets

Diffstat:
A
count_special_triplets.c
 | 
41
+++++++++++++++++++++++++++++++++++++++++
A
count_special_triplets.py
 | 
32
++++++++++++++++++++++++++++++++

2 files changed, 73 insertions(+), 0 deletions(-)
diff --git a/count_special_triplets.c b/count_special_triplets.c
@@ -0,0 +1,41 @@
+// 3583. Count Special Triplets
+#include "leetcode.h"
+
+/*
+ * you are given an integer array 'nums'. a special triplet is defined as a
+ * triplet of indices '(i, j, k)' such that '0 <= i < j < k < n' where 'n =
+ * len(nums)', 'nums[i] == nums[j] * 2', 'nums[k] == nums[j] * 2'. return the
+ * total number of special triplets in the array. since the answer may be very
+ * large, return it modulo 10^9 + 7.
+ */
+
+int specialTriplets(int *nums, int numsSize) {
+  static int mod = 1e9 + 7;
+  int max = 0;
+  for (int i = 0; i < numsSize; ++i)
+    if (max < nums[i])
+      max = nums[i];
+  int max_size = 2 * max + 1;
+  long long *left = (long long *)calloc(max_size, sizeof(long long));
+  long long *right = (long long *)calloc(max_size, sizeof(long long));
+  for (int i = 0; i < numsSize; ++i)
+    right[nums[i]]++;
+  long long ans = 0;
+  for (int i = 0; i < numsSize; i++) {
+    right[nums[i]]--;
+    int val = nums[i] * 2;
+    long long lval = left[val], rval = right[val];
+    ans = (ans + (lval * rval)) % mod;
+    left[nums[i]]++;
+  }
+  free(left);
+  free(right);
+  return (int)ans;
+}
+
+int main() {
+  int n1[] = {6, 3, 6}, n2[] = {0, 1, 0, 0}, n3[] = {8, 4, 2, 8, 4};
+  printf("%d\n", specialTriplets(n1, ARRAY_SIZE(n1))); // expect: 1
+  printf("%d\n", specialTriplets(n2, ARRAY_SIZE(n2))); // expect: 1
+  printf("%d\n", specialTriplets(n3, ARRAY_SIZE(n3))); // expect: 2
+}
diff --git a/count_special_triplets.py b/count_special_triplets.py
@@ -0,0 +1,32 @@
+# 3583. Count Special Triplets
+from collections import Counter
+
+"""
+you are given an integer array 'nums'. a special triplet is defined as a
+triplet of indices '(i, j, k)' such that '0 <= i < j < k < n' where 'n =
+len(nums)', 'nums[i] == nums[j]  2', 'nums[k] == nums[j]  2'. return the
+total number of special triplets in the array. since the answer may be very
+large, return it modulo 10^9 + 7.
+"""
+
+
+class Solution(object):
+    def specialTriplets(self, nums):
+        """
+        :type nums: List[int]
+        :rtype: int
+        """
+        left, right = Counter(), Counter()
+        ans, mod = 0, 10**9 + 7
+        for i in nums:
+            ans += right[i // 2] if i % 2 == 0 else 0
+            right[i] += left[i * 2]
+            left[i] += 1
+        return ans % mod
+
+
+if __name__ == "__main__":
+    obj = Solution()
+    print(obj.specialTriplets(nums=[6, 3, 6]))
+    print(obj.specialTriplets(nums=[0, 1, 0, 0]))
+    print(obj.specialTriplets(nums=[8, 4, 2, 8, 4]))