diff options
Diffstat (limited to 'count_good_triplet_arr.c')
-rw-r--r-- | count_good_triplet_arr.c | 64 |
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 +} |