Count Good Triplets in an Array
Problem
You are given two 0-indexed arrays nums1 and nums2, each a permutation of [0, 1, ..., n − 1]. A good triplet is a set of 3 distinct values that appear in increasing order by position in both arrays. Let pos1[v] and pos2[v] be the index of value v in each array; count triplets (x, y, z) with pos1[x] < pos1[y] < pos1[z] and pos2[x] < pos2[y] < pos2[z]. Return the total number of good triplets.
nums1 = [4,0,1,3,2], nums2 = [4,1,0,2,3]4nums1 = [2,0,1,3], nums2 = [0,1,2,3]1def good_triplets(nums1, nums2):
n = len(nums1)
pos1 = [0] * n
for i, v in enumerate(nums1):
pos1[v] = i
mapped = [pos1[v] for v in nums2]
bit = [0] * (n + 1)
def update(i):
i += 1
while i <= n:
bit[i] += 1
i += i & (-i)
def query(i):
s, i = 0, i + 1
while i > 0:
s += bit[i]
i -= i & (-i)
return s
ans = 0
for j, m in enumerate(mapped):
left = query(m)
right = (n - 1 - j) - (m - left)
ans += left * right
update(m)
return ansfunction goodTriplets(nums1, nums2) {
const n = nums1.length;
const pos1 = new Array(n);
for (let i = 0; i < n; i++) pos1[nums1[i]] = i;
const mapped = nums2.map(v => pos1[v]);
const bit = new Array(n + 1).fill(0);
const update = (i) => {
for (i++; i <= n; i += i & (-i)) bit[i]++;
};
const query = (i) => {
let s = 0;
for (i++; i > 0; i -= i & (-i)) s += bit[i];
return s;
};
let ans = 0;
for (let j = 0; j < n; j++) {
const m = mapped[j];
const left = query(m);
const right = (n - 1 - j) - (m - left);
ans += left * right;
update(m);
}
return ans;
}long goodTriplets(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] pos1 = new int[n];
for (int i = 0; i < n; i++) pos1[nums1[i]] = i;
int[] bit = new int[n + 1];
long ans = 0;
for (int j = 0; j < n; j++) {
int m = pos1[nums2[j]];
int left = query(bit, m);
long right = (n - 1 - j) - (long)(m - left);
ans += (long) left * right;
update(bit, m, n);
}
return ans;
}
void update(int[] bit, int i, int n) {
for (i++; i <= n; i += i & (-i)) bit[i]++;
}
int query(int[] bit, int i) {
int s = 0;
for (i++; i > 0; i -= i & (-i)) s += bit[i];
return s;
}long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> pos1(n), bit(n + 1, 0);
for (int i = 0; i < n; i++) pos1[nums1[i]] = i;
auto update = [&](int i) {
for (i++; i <= n; i += i & (-i)) bit[i]++;
};
auto query = [&](int i) {
int s = 0;
for (i++; i > 0; i -= i & (-i)) s += bit[i];
return s;
};
long long ans = 0;
for (int j = 0; j < n; j++) {
int m = pos1[nums2[j]];
int left = query(m);
long long right = (n - 1 - j) - (long long)(m - left);
ans += (long long) left * right;
update(m);
}
return ans;
}Explanation
A brute force over all triplets is O(n³), far too slow for n up to 10⁵. The trick is to relabel by position so the two constraints collapse into one.
Build pos1[v] = the index of value v in nums1. Now walk nums2 from left to right (this enforces pos2[x] < pos2[y] < pos2[z] automatically) and replace each value with its position in nums1, giving a sequence mapped. A good triplet is exactly an increasing triple in mapped, because increasing in mapped means increasing pos1 too.
Count increasing triples by fixing the middle element. For the j-th element with value m = mapped[j], let left = how many earlier elements are smaller than m, and right = how many later elements are larger than m. The number of triples with this middle is left × right; sum over all j.
A Fenwick tree (BIT) over the value range gives left in O(log n): query how many inserted values are ≤ m, then insert m. Because the values are a permutation, the count of values smaller than m on the right side is just m − left, so right = (n − 1 − j) − (m − left) needs no second tree.
The visualizer walks the mapped sequence, highlighting the smaller-on-the-left elements (blue) and larger-on-the-right elements (green) for each middle, and accumulates left × right into the running answer.