Count Good Triplets in an Array
Count Good Triplets in an Array is a hard arrays & hashing problem solved with the fenwick tree (bit) pattern.
The best approach, optimal (fenwick tree over positions), runs in O(n log n) time and O(n) space.
Below are 3 approaches in Java, Python, C++ and JavaScript, from brute force (try every triple) up.
Problem
You are given two arrays nums1 and nums2 of length n, each a permutation of 0, 1, …, n - 1.
Call a triplet of distinct values (x, y, z) good when the three values appear in the order x, y, z (left to right) in nums1 and also in that same order in nums2. Return the number of good triplets.
Examples
Example 1
- Input
nums1 = [2, 0, 1, 3], nums2 = [0, 2, 1, 3]- Output
2- Why
- (2, 1, 3) and (0, 1, 3) appear in that order in both arrays. Any triplet using both 2 and 0 fails, since they swap places between the arrays.
Example 2
- Input
nums1 = [0, 1, 2, 3], nums2 = [0, 1, 2, 3]- Output
4- Why
- The arrays are identical, so every choice of 3 values out of 4 is good.
Example 3
- Input
nums1 = [0, 1, 2], nums2 = [2, 1, 0]- Output
0- Why
- The arrays list the values in opposite orders, so no two values appear in the same order in both, let alone three.
Constraints
3 <= n <= 10^5wheren == nums1.length == nums2.lengthnums1andnums2are both permutations of0, 1, …, n - 1.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 10 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (try every triple) | O(n³) | O(n) |
| Fix the middle element | O(n²) | O(n) |
| Optimal (Fenwick tree over positions) | O(n log n) | O(n) |
1Brute force (try every triple)
O(n³)C(n, 3) triples are checked.O(n)pos2 and arr.Let pos2[v] be the index of value v in nums2 and build arr[i] = pos2[nums1[i]]. A triple of indices i < j < k in nums1 is good exactly when arr[i] < arr[j] < arr[k]. Check all triples.
- Build pos2 and arr.
- For every i < j < k, count it if arr[i] < arr[j] < arr[k].
class Solution {
public long goodTriplets(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] pos2 = new int[n];
for (int i = 0; i < n; i++) pos2[nums2[i]] = i;
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = pos2[nums1[i]];
long count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
if (arr[j] <= arr[i]) continue;
for (int k = j + 1; k < n; k++)
if (arr[k] > arr[j]) count++;
}
return count;
}
}class Solution:
def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
pos2 = [0] * n
for i, v in enumerate(nums2):
pos2[v] = i
arr = [pos2[v] for v in nums1]
count = 0
for i in range(n):
for j in range(i + 1, n):
if arr[j] <= arr[i]:
continue
for k in range(j + 1, n):
if arr[k] > arr[j]:
count += 1
return countclass Solution {
public:
long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> pos2(n), arr(n);
for (int i = 0; i < n; i++) pos2[nums2[i]] = i;
for (int i = 0; i < n; i++) arr[i] = pos2[nums1[i]];
long long count = 0;
for (int i = 0; i < n; i++)
for (int j = i + 1; j < n; j++) {
if (arr[j] <= arr[i]) continue;
for (int k = j + 1; k < n; k++)
if (arr[k] > arr[j]) count++;
}
return count;
}
};function goodTriplets(nums1, nums2) {
const n = nums1.length;
const pos2 = new Array(n);
for (let i = 0; i < n; i++) pos2[nums2[i]] = i;
const arr = nums1.map((v) => pos2[v]);
let count = 0;
for (let i = 0; i < n; i++)
for (let j = i + 1; j < n; j++) {
if (arr[j] <= arr[i]) continue;
for (let k = j + 1; k < n; k++)
if (arr[k] > arr[j]) count++;
}
return count;
}2Fix the middle element
O(n²)Two linear scans for each of the n middles.O(n)pos2 and arr.For each middle index j of arr, count the indices to its left with a smaller value and the indices to its right with a larger value. Every pairing of one from each side gives a good triplet, so add the product.
- Build arr as before.
- For each j: left = #{i < j : arr[i] < arr[j]}, right = #{k > j : arr[k] > arr[j]}.
- Add left × right to the answer.
class Solution {
public long goodTriplets(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] pos2 = new int[n];
for (int i = 0; i < n; i++) pos2[nums2[i]] = i;
int[] arr = new int[n];
for (int i = 0; i < n; i++) arr[i] = pos2[nums1[i]];
long total = 0;
for (int j = 0; j < n; j++) {
long left = 0, right = 0;
for (int i = 0; i < j; i++) if (arr[i] < arr[j]) left++;
for (int k = j + 1; k < n; k++) if (arr[k] > arr[j]) right++;
total += left * right;
}
return total;
}
}class Solution:
def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
pos2 = [0] * n
for i, v in enumerate(nums2):
pos2[v] = i
arr = [pos2[v] for v in nums1]
total = 0
for j in range(n):
left = sum(1 for i in range(j) if arr[i] < arr[j])
right = sum(1 for k in range(j + 1, n) if arr[k] > arr[j])
total += left * right
return totalclass Solution {
public:
long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> pos2(n), arr(n);
for (int i = 0; i < n; i++) pos2[nums2[i]] = i;
for (int i = 0; i < n; i++) arr[i] = pos2[nums1[i]];
long long total = 0;
for (int j = 0; j < n; j++) {
long long left = 0, right = 0;
for (int i = 0; i < j; i++) if (arr[i] < arr[j]) left++;
for (int k = j + 1; k < n; k++) if (arr[k] > arr[j]) right++;
total += left * right;
}
return total;
}
};function goodTriplets(nums1, nums2) {
const n = nums1.length;
const pos2 = new Array(n);
for (let i = 0; i < n; i++) pos2[nums2[i]] = i;
const arr = nums1.map((v) => pos2[v]);
let total = 0;
for (let j = 0; j < n; j++) {
let left = 0, right = 0;
for (let i = 0; i < j; i++) if (arr[i] < arr[j]) left++;
for (let k = j + 1; k < n; k++) if (arr[k] > arr[j]) right++;
total += left * right;
}
return total;
}3Optimal (Fenwick tree over positions)
O(n log n)One Fenwick query and one update per index, each O(log n).O(n)The Fenwick tree plus pos2 and arr.Scan arr from left to right with a Fenwick (binary indexed) tree that marks the values already seen. At index j, a prefix query gives left = how many seen values are smaller than arr[j]. Of the j values to the left, j - left are larger, and there are n - 1 - arr[j] larger values overall, so right = (n - 1 - arr[j]) - (j - left). Add left × right.
- Build arr[i] = pos2[nums1[i]].
- For j = 0..n-1: left = query(arr[j] - 1); right = (n - 1 - arr[j]) - (j - left).
- total += left × right; then add 1 at position arr[j].
- Return total.
class Solution {
public long goodTriplets(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] pos2 = new int[n];
for (int i = 0; i < n; i++) pos2[nums2[i]] = i;
int[] tree = new int[n + 1];
long total = 0;
for (int j = 0; j < n; j++) {
int p = pos2[nums1[j]];
long left = 0;
for (int x = p; x > 0; x -= x & -x) left += tree[x];
long right = (n - 1 - p) - (j - left);
total += left * right;
for (int x = p + 1; x <= n; x += x & -x) tree[x]++;
}
return total;
}
}class Solution:
def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
n = len(nums1)
pos2 = [0] * n
for i, v in enumerate(nums2):
pos2[v] = i
tree = [0] * (n + 1)
total = 0
for j, v in enumerate(nums1):
p = pos2[v]
left = 0
x = p
while x > 0:
left += tree[x]
x -= x & -x
right = (n - 1 - p) - (j - left)
total += left * right
x = p + 1
while x <= n:
tree[x] += 1
x += x & -x
return totalclass Solution {
public:
long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
vector<int> pos2(n), tree(n + 1, 0);
for (int i = 0; i < n; i++) pos2[nums2[i]] = i;
long long total = 0;
for (int j = 0; j < n; j++) {
int p = pos2[nums1[j]];
long long left = 0;
for (int x = p; x > 0; x -= x & -x) left += tree[x];
long long right = (long long)(n - 1 - p) - (j - left);
total += left * right;
for (int x = p + 1; x <= n; x += x & -x) tree[x]++;
}
return total;
}
};function goodTriplets(nums1, nums2) {
const n = nums1.length;
const pos2 = new Int32Array(n);
for (let i = 0; i < n; i++) pos2[nums2[i]] = i;
const tree = new Int32Array(n + 1);
let total = 0;
for (let j = 0; j < n; j++) {
const p = pos2[nums1[j]];
let left = 0;
for (let x = p; x > 0; x -= x & -x) left += tree[x];
const right = (n - 1 - p) - (j - left);
total += left * right;
for (let x = p + 1; x <= n; x += x & -x) tree[x]++;
}
return total;
}Edge cases to test
- n = 3: the answer is 0 or 1
- Identical arrays: every one of the C(n, 3) triplets is good
- One array reversed relative to the other: answer 0
- Large n: the answer exceeds 32 bits, so use a 64-bit result
Hints
Hint 1
Rename values by their position in nums2. Then a triplet is good exactly when the renamed values form an increasing subsequence of length 3 inside nums1.
Hint 2
Fix the middle element. The number of good triplets with that middle is (smaller values to its left) × (larger values to its right).
Hint 3
Count 'smaller values to the left' for every index with a Fenwick tree over values while scanning left to right; the 'larger to the right' count follows by arithmetic.
FAQ
What is the best time complexity for Count Good Triplets in an Array?
Optimal (Fenwick tree over positions) runs in O(n log n) time and O(n) extra space. One Fenwick query and one update per index, each O(log n).
Which pattern does Count Good Triplets in an Array use?
It is a arrays & hashing problem that uses the fenwick tree (bit) pattern.
Is there a brute force solution for Count Good Triplets in an Array?
Yes. Brute force (try every triple) takes O(n³) time and O(n) space. Let pos2[v] be the index of value v in nums2 and build arr[i] = pos2[nums1[i]].
Which edge cases should I test for Count Good Triplets in an Array?
n = 3: the answer is 0 or 1; Identical arrays: every one of the C(n, 3) triplets is good; One array reversed relative to the other: answer 0; Large n: the answer exceeds 32 bits, so use a 64-bit result.