aboutsummaryrefslogtreecommitdiff
path: root/count_good_triplet_arr.c
diff options
context:
space:
mode:
Diffstat (limited to 'count_good_triplet_arr.c')
-rw-r--r--count_good_triplet_arr.c64
1 files changed, 64 insertions, 0 deletions
diff --git a/count_good_triplet_arr.c b/count_good_triplet_arr.c
new file mode 100644
index 0000000..fd32e94
--- /dev/null
+++ b/count_good_triplet_arr.c
@@ -0,0 +1,64 @@
+// 2179. Count Good Triplets in an Array
+#include "leetcode.h"
+
+/*
+ * you are given two 0-indexed arrays 'nums1' and 'nums2' of length 'n', both of
+ * which are permutations of '[0, 1, ..., n - 1]'. a good triplet is a set of
+ * three distinct values which are present in increasing order by position in
+ * both 'nums1' and 'nums2'. in other words, if we consider 'pos1v' as the index
+ * of the value 'v' in 'nums1' and 'pos2v' as the index of the value 'v' in
+ * 'nums2', then a good triplet will be a set '(x, y, z)'. return the total
+ * number of good triplets.
+ */
+
+#define MAX_SIZE 100010
+
+static int tree[MAX_SIZE];
+
+void tree_push(int idx, int val, int n) {
+ idx++;
+ while (idx <= n + 2) {
+ tree[idx] += val;
+ idx += idx & (-idx);
+ }
+}
+
+int tree_query(int idx) {
+ idx++;
+ int res = 0;
+ while (idx > 0) {
+ res += tree[idx];
+ idx -= idx & (-idx);
+ }
+ return res;
+}
+
+long long goodTriplets(int *nums1, int nums1Size, int *nums2, int nums2Size) {
+ int n = nums1Size, p2v[MAX_SIZE], arr[MAX_SIZE], left[MAX_SIZE] = {0};
+ for (int i = 0; i < n; i++)
+ p2v[nums2[i]] = i;
+ for (int i = 0; i < n; i++)
+ arr[i] = p2v[nums1[i]];
+ memset(tree, 0, sizeof(tree));
+ for (int i = 0; i < n; i++) {
+ left[i] = tree_query(arr[i] - 1);
+ tree_push(arr[i], 1, n);
+ }
+ memset(tree, 0, sizeof(tree));
+ long long ans = 0;
+ for (int i = n - 1; i >= 0; i--) {
+ int right = tree_query(n - 1) - tree_query(arr[i]);
+ ans += (long long)left[i] * right;
+ tree_push(arr[i], 1, n);
+ }
+ return ans;
+}
+
+int main() {
+ int n11[] = {2, 0, 1, 3}, n21[] = {0, 1, 2, 3};
+ int n12[] = {4, 0, 1, 3, 2}, n22[] = {4, 1, 0, 2, 3};
+ printf("%lld\n",
+ goodTriplets(n11, ARRAY_SIZE(n11), n21, ARRAY_SIZE(n21))); // expect: 1
+ printf("%lld\n",
+ goodTriplets(n12, ARRAY_SIZE(n12), n22, ARRAY_SIZE(n22))); // expect: 4
+}