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 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) where 0 <= x, y, z <= n - 1, such that pos1x < pos1y < pos1z and pos2x < pos2y < pos2z.
Return the total number of good triplets.
Example 1:
Input: nums1 = [2,0,1,3], nums2 = [0,1,2,3] Output: 1 Explanation: There are 4 triplets (x,y,z) such that pos1x < pos1y < pos1z. 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 pos2x < pos2y < pos2z. Hence, there is only 1 good triplet.
Example 2:
Input: nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3] Output: 4 Explanation: The 4 good triplets are (4,0,3), (4,0,2), (4,1,3), and (4,1,2).
Constraints:
n == nums1.length == nums2.length3 <= n <= 1050 <= nums1[i], nums2[i] <= n - 1nums1andnums2are 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)
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 one 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 in B the numbers smaller than 1 before 1 and numbers greater than 1 after 1.
Count the common numbers before B[i] that are smaller than B[i] (i is 0-indexed):
- In
A, there areB[i]such numbers. - In
B, let's say there arelt[i]such numbers.lt[i] <= B[i]andlt[i] <= i. - So, there are
min(B[i], lt[i]) = lt[i]such numbers in both arrays.
Take B[1] = 2 for example, there are 2 such numbers in A, and lt[1] = 1 such number in B, so there is 1 such numbers in both arrays.
Count the common numbers after B[i] that are greater than B[i]:
- In
A, there areN - B[i] - 1such numbers inA. - In
B, there areN - B[i] - 1numbers inBthat are greater thanB[i]. Among these numbers,i - lt[i]numbers are used beforeB[i]. So, there areN - B[i] - 1 - (i - lt[i]) = N - B[i] - 1 - i + lt[i]such numbers. - So, there are
N - B[i] - 1 - i + lt[i]such numbers in both arrays.
Take B[2] = 1 for example, there are 5 - 1 - 1 = 3 such numbers in A. Among these 3 numbers (2,3,4), i - lt[i] = 2 - 1 = 1 number (2) is used before B[2], so there are N - B[i] - 1 - i + lt[i] = 5 - 1 - 1 - 2 + 1 = 2 such numbers in B and in both arrays.
So, the count of triplets with B[i] as the middle number is lt[i] * (N - B[i] - 1 - i + lt[i])
// OJ: https://leetcode.com/problems/count-good-triplets-in-an-array/
// Author: github.com/lzl124631x
// 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;
}
};// OJ: https://leetcode.com/problems/count-good-triplets-in-an-array/
// Author: github.com/lzl124631x
// 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;
}
};In OOD fashion.
// OJ: https://leetcode.com/problems/count-good-triplets-in-an-array
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(N)
class BIT {
vector<int> node; // node[i] is the count of numbers `<=` i (1-based)
static inline int lb(int x) { return x & -x; }
public:
BIT(int N) : node(N + 1) {}
int query(int i) { // externally `i` is 0-based
int ans = 0;
for (i++; i; i -= lb(i)) ans += node[i];
return ans;
}
void update(int i) {
for (i++; i < node.size(); i += lb(i)) node[i]++;
}
};
class Solution {
public:
long long goodTriplets(vector<int>& A, vector<int>& B) {
long long N = A.size(), ans = 0;
vector<int> m(N);
for (int i = 0; i < N; ++i) m[A[i]] = i;
BIT tree(N);
for (int i = 0; i < N; ++i) {
int n = m[B[i]]; // B[i] is mapped to `n` (0-indexed)
int lt = tree.query(n - 1); // `lt` is count of numbers less than `n`
ans += (long)lt * (N - n - 1 - i + lt);
tree.update(n); // update the presence of `n`
}
return ans;
}
};