Formatted question description: https://leetcode.ca/all/2179.html

# 2179. Count Good Triplets in an Array (Hard)

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 `3`

**distinct** values which are present in **increasing order** by position both in `nums1`

and `nums2`

. In other words, if we consider `pos1`

as the index of the value _{v}`v`

in `nums1`

and `pos2`

as the index of the value _{v}`v`

in `nums2`

, then a good triplet will be a set `(x, y, z)`

where `0 <= x, y, z <= n - 1`

, such that `pos1`

and _{x} < pos1_{y} < pos1_{z}`pos2`

._{x} < pos2_{y} < pos2_{z}

Return *the total number of good triplets*.

**Example 1:**

Input:nums1 = [2,0,1,3], nums2 = [0,1,2,3]Output:1Explanation:There are 4 triplets (x,y,z) such that pos1_{x}< pos1_{y}< pos1_{z}. They are (2,0,1), (2,0,3), (2,1,3), and (0,1,3). Out of those triplets, only the triplet (0,1,3) satisfies pos2_{x}< pos2_{y}< pos2_{z}. Hence, there is only 1 good triplet.

**Example 2:**

Input:nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]Output:4Explanation:The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).

**Constraints:**

`n == nums1.length == nums2.length`

`3 <= n <= 10`

^{5}`0 <= nums1[i], nums2[i] <= n - 1`

`nums1`

and`nums2`

are permutations of`[0, 1, ..., n - 1]`

.

**Similar Questions**:

- Count of Smaller Numbers After Self (Hard)
- Increasing Triplet Subsequence (Medium)
- Create Sorted Array through Instructions (Hard)

## Solution 1. Divide and Conquer (Merge Sort)

The first idea is that we pick a number as the middle number in the triplet, and count the common numbers in front of this number and after this number.

For example,

```
A = [4,0,1,3,2]
B = [4,1,0,2,3]
```

For number `1`

, there is a single common number (`4`

) in front of `1`

and two common numbers (`3,4`

) after `1`

, so the count of triplets with `1`

in the middle is `1 * 2 = 2`

.

But counting the common numbers is not easy. **Since the numbers are permutations of [0, N-1], we can simplify the problem by mapping on of the array to [0, N-1].**

For example, if we map `A`

to `[0, N-1]`

.

```
A = [4,0,1,3,2]
A'= [0,1,2,3,4]
mapping = 4->0, 0->1, 1->2, 3->3, 2->4
```

We apply the same mapping to `B`

```
B = [4,1,0,2,3]
B'= [0,2,1,4,3]
```

Now look at the new arrays

```
A = [0,1,2,3,4]
B = [0,2,1,4,3]
```

For the number `1`

, we trivially know that in `A`

, there is one number `0`

before it and 3 numbers `2,3,4`

after it. So, we just need to look at `B`

. The problem now becomes counting the numbers smaller than `1`

before `1`

and numbers greater than `1`

after `1`

.

Let `lt[i]`

be the count of numbers smaller than `B[i]`

. The count of common numbers before `B[i]`

is `min(B[i], lt[i]) = lt[i]`

. The count of common numbers after `B[i]`

in `A`

is `N - B[i] - 1`

. The count of common numbers after `B[i]`

in `B`

is `N - i - 1 - (B[i] - lt[i]) = N - B[i] - 1 - i + lt[i]`

. Since `i >= lt[i]`

, `-i + lt[i] <= 0`

, the count of common numbers after `B[i]`

in both arrays is `N - B[i] - 1 - i + lt[i]`

.

So, the count of triplets with `B[i]`

as the middle number is `min(B[i], lt[i]) * (N - B[i] - 1 - i + lt[i])`

```
// OJ: https://leetcode.com/problems/count-good-triplets-in-an-array/
// Time: O(NlogN)
// Space: O(N)
class Solution {
public:
long long goodTriplets(vector<int>& A, vector<int>& B) {
long N = A.size(), ans = 0;
vector<int> m(N), lt(N), tmp(N), tmpLt(N), index(N);
for (int i = 0; i < N; ++i) m[A[i]] = i;
for (int i = 0; i < N; ++i) {
B[i] = m[B[i]];
index[B[i]] = i;
}
function<void(int, int)> merge = [&](int begin, int end) {
if (begin + 1 >= end) return;
int mid = (begin + end) / 2;
merge(begin, mid);
merge(mid, end);
int i = begin, j = mid, k = begin;
for (; k < end; ++k) {
if (j >= end || (i < mid && B[i] < B[j])) {
tmp[k] = B[i];
tmpLt[k] = lt[i];
++i;
} else {
tmp[k] = B[j];
tmpLt[k] = lt[j] + i - begin;
++j;
}
}
for (int i = begin; i < end; ++i) {
B[i] = tmp[i];
lt[i] = tmpLt[i];
}
};
merge(0, N);
for (int i = 0; i < N; ++i) {
ans += (long)lt[i] * (N - B[i] - 1 - index[B[i]] + lt[i]);
}
return ans;
}
};
```

## Solution 2. Binary Index Tree

```
// OJ: https://leetcode.com/problems/count-good-triplets-in-an-array/
// Time: O(NlogN)
// Space: O(N)
// Ref: https://leetcode-cn.com/problems/count-good-triplets-in-an-array/solution/deng-jie-zhuan-huan-shu-zhuang-shu-zu-by-xmyd/
class Solution {
public:
long long goodTriplets(vector<int> &A, vector<int> &B) {
int N = A.size();
vector<int> m(N);
for (int i = 0; i < N; ++i) m[A[i]] = i;
long long ans = 0;
vector<int> tree(N + 1);
for (int i = 1; i < N - 1; ++i) {
for (int j = m[B[i - 1]] + 1; j <= N; j += j & -j) ++tree[j]; // increment the count of m[B[i-1]]
int y = m[B[i]], less = 0;
for (int j = y; j; j &= j - 1) less += tree[j]; // count all the numbers less than m[B[i]]
ans += (long)less * (N - 1 - y - (i - less));
}
return ans;
}
};
```