Count Good Triplets in an Array solution and explanation
Google
9 more videos on this problem
Count Good Triplets in an Array | Segment Tree Concepts & Qns | Video 12 | Leetcode 2179 | MIKcodestorywithMIK · 1:04:09 · 16K views
Count Good Triplets in an Array | Leetcode 2179 | Segment TreeTechdose · 47:22 · 8K views
2179. Count Good Triplets in an Array || Biweekly Contest 72 || Leetcode 2179 || PDS approachBro Coders · 18:13 · 6K views
Count Good Triplets in an Array | 2179 LeetCode | Data Structures | Leetcode BiWeekly Contest 72CodeWithSunny · 30:12 · 2K views
Daily Leetcode #1841: Apr 15, 2025 - 2179. Count Good Triplets in an ArrayProgramming Live with Larry · 21:43 · 1K views
12179. Count Good Triplets in an Array | Leetcode Daily - PythonLeetcode Daily · 16:09 · 1K views
2179. Count Good Triplets in an Array (Leetcode Hard)Programming Live with Larry · 48:15 · 1K views
LeetCode 2179 - Count Good Triplets | Fenwick Tree Explained | Advanced Coding Interview ProblemStatLearn Tech · 25:58 · 958 views
Luffy Solves LeetCode 2179: Count Good Triplets with Smart Navigation (NOT Brute Force!)Code Crusaders · 4:30 · 623 views
LeetCode 2179 - Count Good Triplets In An Array - PythonAlpha-Code · 16:24 · 572 views
The problem
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].
Approach overview
Problem Overview: You receive two permutations nums1 and nums2 of length n. A triplet (i, j, k) is considered good if i < j < k and the relative order of the values in nums2 is also increasing. The task reduces to counting how many index triplets maintain the same ordering in both arrays.
The key observation: instead of comparing elements across two arrays repeatedly, map each value in nums1 to its index in nums2. This converts the problem into counting increasing triplets in a single array of positions.
Approach 1: Brute Force Enumeration (O(n³) time, O(1) space)
Check every possible triple (i, j, k) with three nested loops. For each triplet, compare their positions in nums2 and verify the order constraint. This works because both arrays contain the same elements. The approach is simple and confirms the definition of a good triplet, but the cubic runtime becomes impractical even for moderate n. Still useful for reasoning about the problem and validating smaller test cases.
Approach 2: Relative Position Array + Binary Indexed Tree (O(n log n) time, O(n) space)
Create a map from value to index in nums2. Transform nums1 into a new array pos where pos[i] represents the position of nums1[i] inside nums2. Now the task becomes counting increasing triplets in pos. For each index j, compute how many values smaller than pos[j] appear to the left and how many larger values appear to the right. Multiply these counts to determine how many triplets use j as the middle element.
A Binary Indexed Tree efficiently maintains prefix counts while iterating. Each query finds how many processed elements are smaller than the current position, and updates insert the current position into the structure. This converts the naive counting problem into logarithmic updates and queries.
Other structures like a Segment Tree or divide-and-conquer methods such as merge-based counting from divide and conquer can solve the same increasing-triplet counting task with similar O(n log n) complexity.
Recommended for interviews: The relative position + Binary Indexed Tree approach is the expected solution. Interviewers want to see that you recognize the permutation mapping trick and reduce the problem to counting increasing subsequence triplets. Mentioning the brute force method shows you understand the baseline, but implementing the O(n log n) counting solution demonstrates strong data structure skills.
Approach 1: Brute Force Approach
In this approach, we try all possible triplets (x, y, z) and check if they satisfy the good triplet condition.
def find_pos(arr, value):
return arr.index(value)
def count_good_triplets(nums1, nums2):
n = len(nums1)
count = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
pos1_i = find_pos(nums1, nums1[i])
pos1_j = find_pos(nums1, nums1[j])
pos1_k = find_pos(nums1, nums1[k])
pos2_i = find_pos(nums2, nums2[i])
pos2_j = find_pos(nums2, nums2[j])
pos2_k = find_pos(nums2, nums2[k])
if pos1_i < pos1_j < pos1_k and pos2_i < pos2_j < pos2_k:
count += 1
return count
nums1 = [2, 0, 1, 3]
nums2 = [0, 1, 2, 3]
print(count_good_triplets(nums1, nums2))public class GoodTriplets {
public static int findPos(int[] arr, int value) {
for (int i = 0; i < arr.length; i++) {
if (arr[i] == value) return i;
}
return -1;
}
public static int countGoodTriplets(int[] nums1, int[] nums2) {
int n = nums1.length;
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int pos1_i = findPos(nums1, nums1[i]);
int pos1_j = findPos(nums1, nums1[j]);
int pos1_k = findPos(nums1, nums1[k]);
int pos2_i = findPos(nums2, nums2[i]);
int pos2_j = findPos(nums2, nums2[j]);
int pos2_k = findPos(nums2, nums2[k]);
if (pos1_i < pos1_j && pos1_j < pos1_k && pos2_i < pos2_j && pos2_j < pos2_k) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums1 = {2, 0, 1, 3};
int[] nums2 = {0, 1, 2, 3};
System.out.println(countGoodTriplets(nums1, nums2));
}
}#include <iostream>
#include <vector>
using namespace std;
int findPos(const vector<int>& arr, int value) {
for (int i = 0; i < arr.size(); i++) {
if (arr[i] == value) return i;
}
return -1;
}
int countGoodTriplets(const vector<int>& nums1, const vector<int>& nums2) {
int n = nums1.size();
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int pos1_i = findPos(nums1, nums1[i]);
int pos1_j = findPos(nums1, nums1[j]);
int pos1_k = findPos(nums1, nums1[k]);
int pos2_i = findPos(nums2, nums2[i]);
int pos2_j = findPos(nums2, nums2[j]);
int pos2_k = findPos(nums2, nums2[k]);
if (pos1_i < pos1_j && pos1_j < pos1_k && pos2_i < pos2_j && pos2_j < pos2_k) {
count++;
}
}
}
}
return count;
}
int main() {
vector<int> nums1 = {2, 0, 1, 3};
vector<int> nums2 = {0, 1, 2, 3};
cout << countGoodTriplets(nums1, nums2) << endl;
return 0;
}function findPos(arr, value) {
return arr.indexOf(value);
}
function countGoodTriplets(nums1, nums2) {
let n = nums1.length;
let count = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
let pos1_i = findPos(nums1, nums1[i]);
let pos1_j = findPos(nums1, nums1[j]);
let pos1_k = findPos(nums1, nums1[k]);
let pos2_i = findPos(nums2, nums2[i]);
let pos2_j = findPos(nums2, nums2[j]);
let pos2_k = findPos(nums2, nums2[k]);
if (pos1_i < pos1_j && pos1_j < pos1_k &&
pos2_i < pos2_j && pos2_j < pos2_k) {
count++;
}
}
}
}
return count;
}
let nums1 = [2, 0, 1, 3];
let nums2 = [0, 1, 2, 3];
console.log(countGoodTriplets(nums1, nums2));#include <stdio.h>
int findPos(int arr[], int n, int value) {
for (int i = 0; i < n; i++) {
if (arr[i] == value) return i;
}
return -1;
}
int countGoodTriplets(int* nums1, int* nums2, int n) {
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
int pos1_i = findPos(nums1, n, nums1[i]);
int pos1_j = findPos(nums1, n, nums1[j]);
int pos1_k = findPos(nums1, n, nums1[k]);
int pos2_i = findPos(nums2, n, nums2[i]);
int pos2_j = findPos(nums2, n, nums2[j]);
int pos2_k = findPos(nums2, n, nums2[k]);
if (pos1_i < pos1_j && pos1_j < pos1_k && pos2_i < pos2_j && pos2_j < pos2_k) {
count++;
}
}
}
}
return count;
}
int main() {
int nums1[] = {2, 0, 1, 3};
int nums2[] = {0, 1, 2, 3};
int n = 4;
printf("%d\n", countGoodTriplets(nums1, nums2, n));
return 0;
}using System;
class GoodTriplets {
private static int FindPos(int[] arr, int value) {
for (int i = 0; i < arr.Length; i++) {
if (arr[i] == value) return i;
}
return -1;
}
public static int CountGoodTriplets(int[] nums1, int[] nums2) {
int n = nums1.Length;
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (FindPos(nums1, nums1[i]) < FindPos(nums1, nums1[j]) &&
FindPos(nums1, nums1[j]) < FindPos(nums1, nums1[k]) &&
FindPos(nums2, nums2[i]) < FindPos(nums2, nums2[j]) &&
FindPos(nums2, nums2[j]) < FindPos(nums2, nums2[k])) {
count++;
}
}
}
}
return count;
}
public static void Main(string[] args) {
int[] nums1 = {2, 0, 1, 3};
int[] nums2 = {0, 1, 2, 3};
Console.WriteLine(CountGoodTriplets(nums1, nums2));
}
}In this Python solution, we use list.index() to find the positions and then compare the triplet combinations in both arrays.
Time Complexity: O(n^3), Space Complexity: O(1)
Approach 2: Optimized Approach Using Relative Position Arrays
Instead of checking every possible triplet, we utilize position arrays to track indices, reducing unnecessary checks and improving efficiency.
def count_good_triplets(nums1, nums2):
n = len(nums1)
pos1 = [0] * n
pos2 = [0] * n
for i in range(n):
pos1[nums1[i]] = i
pos2[nums2[i]] = i
count = 0
for i in range(n):
for j in range(i + 1, n):
for k in range(j + 1, n):
if pos1[i] < pos1[j] < pos1[k] and pos2[i] < pos2[j] < pos2[k]:
count += 1
return count
nums1 = [2, 0, 1, 3]
nums2 = [0, 1, 2, 3]
print(count_good_triplets(nums1, nums2))import java.util.*;
public class GoodTriplets {
public static int countGoodTriplets(int[] nums1, int[] nums2) {
int n = nums1.length;
int[] pos1 = new int[n], pos2 = new int[n];
for (int i = 0; i < n; i++) {
pos1[nums1[i]] = i;
pos2[nums2[i]] = i;
}
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (pos1[i] < pos1[j] && pos1[j] < pos1[k] && pos2[i] < pos2[j] && pos2[j] < pos2[k]) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
int[] nums1 = {2, 0, 1, 3};
int[] nums2 = {0, 1, 2, 3};
System.out.println(countGoodTriplets(nums1, nums2));
}
}#include <iostream>
#include <vector>
using namespace std;
int countGoodTriplets(const vector<int>& nums1, const vector<int>& nums2) {
int n = nums1.size();
vector<int> pos1(n), pos2(n);
for (int i = 0; i < n; i++) {
pos1[nums1[i]] = i;
pos2[nums2[i]] = i;
}
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (pos1[i] < pos1[j] && pos1[j] < pos1[k] && pos2[i] < pos2[j] && pos2[j] < pos2[k]) {
count++;
}
}
}
}
return count;
}
int main() {
vector<int> nums1 = {2, 0, 1, 3};
vector<int> nums2 = {0, 1, 2, 3};
cout << countGoodTriplets(nums1, nums2) << endl;
return 0;
}function countGoodTriplets(nums1, nums2) {
const n = nums1.length;
const pos1 = new Array(n);
const pos2 = new Array(n);
for (let i = 0; i < n; i++) {
pos1[nums1[i]] = i;
pos2[nums2[i]] = i;
}
let count = 0;
for (let i = 0; i < n; i++) {
for (let j = i + 1; j < n; j++) {
for (let k = j + 1; k < n; k++) {
if (pos1[i] < pos1[j] && pos1[j] < pos1[k] && pos2[i] < pos2[j] && pos2[j] < pos2[k]) {
count++;
}
}
}
}
return count;
}
const nums1 = [2, 0, 1, 3];
const nums2 = [0, 1, 2, 3];
console.log(countGoodTriplets(nums1, nums2));#include <stdio.h>
#include <string.h>
#define MAX 100000
int countGoodTriplets(int *nums1, int *nums2, int n) {
int pos1[MAX], pos2[MAX];
for (int i = 0; i < n; i++) {
pos1[nums1[i]] = i;
pos2[nums2[i]] = i;
}
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (pos1[i] < pos1[j] && pos1[j] < pos1[k] && pos2[i] < pos2[j] && pos2[j] < pos2[k]) {
count++;
}
}
}
}
return count;
}
int main() {
int nums1[] = {2, 0, 1, 3};
int nums2[] = {0, 1, 2, 3};
int n = 4;
printf("%d\n", countGoodTriplets(nums1, nums2, n));
return 0;
}using System;
class GoodTriplets {
public static int CountGoodTriplets(int[] nums1, int[] nums2) {
int n = nums1.Length;
int[] pos1 = new int[n], pos2 = new int[n];
for (int i = 0; i < n; i++) {
pos1[nums1[i]] = i;
pos2[nums2[i]] = i;
}
int count = 0;
for (int i = 0; i < n; i++) {
for (int j = i + 1; j < n; j++) {
for (int k = j + 1; k < n; k++) {
if (pos1[i] < pos1[j] && pos1[j] < pos1[k] && pos2[i] < pos2[j] && pos2[j] < pos2[k]) {
count++;
}
}
}
}
return count;
}
static void Main(string[] args) {
int[] nums1 = {2, 0, 1, 3};
int[] nums2 = {0, 1, 2, 3};
Console.WriteLine(CountGoodTriplets(nums1, nums2));
}
}This Python version uses precomputed position indices to decrease the overall complexity of checking permissible triplet combinations.
Time Complexity: O(n^2), Space Complexity: O(n)
Approach 3: Binary Indexed Tree (Fenwick Tree)
For this problem, we first use pos to record the position of each number in nums2, and then process each element in nums1 sequentially.
Consider the number of good triplets with the current number as the middle number. The first number must have already been traversed and must appear earlier than the current number in nums2. The third number must not yet have been traversed and must appear later than the current number in nums2.
Take nums1 = [4,0,1,3,2] and nums2 = [4,1,0,2,3] as an example. Consider the traversal process:
- First, process
4. At this point, the state ofnums2is[4,X,X,X,X]. The number of values before4is0, and the number of values after4is4. Therefore,4as the middle number forms0good triplets. - Next, process
0. The state ofnums2becomes[4,X,0,X,X]. The number of values before0is1, and the number of values after0is2. Therefore,0as the middle number forms2good triplets. - Next, process
1. The state ofnums2becomes[4,1,0,X,X]. The number of values before1is1, and the number of values after1is2. Therefore,1as the middle number forms2good triplets. - ...
- Finally, process
2. The state ofnums2becomes[4,1,0,2,3]. The number of values before2is4, and the number of values after2is0. Therefore,2as the middle number forms0good triplets.
We can use a Binary Indexed Tree (Fenwick Tree) to update the occurrence of numbers at each position in nums2, and quickly calculate the number of 1s to the left of each number and the number of 0s to the right of each number.
A Binary Indexed Tree, also known as a Fenwick Tree, efficiently supports the following operations:
- Point Update
update(x, delta): Add a valuedeltato the number at positionxin the sequence. - Prefix Sum Query
query(x): Query the sum of the sequence in the range[1, ..., x], i.e., the prefix sum at positionx.
Both operations have a time complexity of O(log n). Therefore, the overall time complexity is O(n log n), where n is the length of the array nums1. The space complexity is O(n).
class BinaryIndexedTree {
private c: number[];
private n: number;
constructor(n: number) {
this.n = n;
this.c = Array(n + 1).fill(0);
}
private static lowbit(x: number): number {
return x & -x;
}
update(x: number, delta: number): void {
while (x <= this.n) {
this.c[x] += delta;
x += BinaryIndexedTree.lowbit(x);
}
}
query(x: number): number {
let s = 0;
while (x > 0) {
s += this.c[x];
x -= BinaryIndexedTree.lowbit(x);
}
return s;
}
}
function goodTriplets(nums1: number[], nums2: number[]): number {
const n = nums1.length;
const pos = new Map<number, number>();
nums2.forEach((v, i) => pos.set(v, i + 1));
const tree = new BinaryIndexedTree(n);
let ans = 0;
for (const num of nums1) {
const p = pos.get(num)!;
const left = tree.query(p);
const total = tree.query(n);
const right = n - p - (total - left);
ans += left * right;
tree.update(p, 1);
}
return ans;
}type BinaryIndexedTree struct {
n int
c []int
}
func newBinaryIndexedTree(n int) *BinaryIndexedTree {
c := make([]int, n+1)
return &BinaryIndexedTree{n, c}
}
func (this *BinaryIndexedTree) lowbit(x int) int {
return x & -x
}
func (this *BinaryIndexedTree) update(x, delta int) {
for x <= this.n {
this.c[x] += delta
x += this.lowbit(x)
}
}
func (this *BinaryIndexedTree) query(x int) int {
s := 0
for x > 0 {
s += this.c[x]
x -= this.lowbit(x)
}
return s
}
func goodTriplets(nums1 []int, nums2 []int) int64 {
n := len(nums1)
pos := make([]int, n)
for i, v := range nums2 {
pos[v] = i + 1
}
tree := newBinaryIndexedTree(n)
var ans int64
for _, num := range nums1 {
p := pos[num]
left := tree.query(p)
right := n - p - (tree.query(n) - tree.query(p))
ans += int64(left) * int64(right)
tree.update(p, 1)
}
return ans
}Approach 4: Segment Tree
We can also use a segment tree to solve this problem. A segment tree is a data structure that efficiently supports range queries and updates. The basic idea is to divide an interval into multiple subintervals, with each subinterval represented by a node.
The segment tree divides the entire interval into multiple non-overlapping subintervals, with the number of subintervals not exceeding log(width). To update the value of an element, we only need to update log(width) intervals, all of which are contained within a larger interval that includes the element.
- Each node of the segment tree represents an interval.
- The segment tree has a unique root node, representing the entire range, such as
[1, N]. - Each leaf node of the segment tree represents a unit interval
[x, x]. - For each internal node
[l, r], its left child represents[l, mid], and its right child represents[mid + 1, r], wheremid = ⌊(l + r) / 2⌋(floor division).
The time complexity is O(n log n), where n is the length of the array nums1. The space complexity is O(n).
class Node {
l: number = 0;
r: number = 0;
v: number = 0;
}
class SegmentTree {
private tr: Node[];
constructor(n: number) {
this.tr = Array(4 * n);
for (let i = 0; i < 4 * n; i++) {
this.tr[i] = new Node();
}
this.build(1, 1, n);
}
private build(u: number, l: number, r: number): void {
this.tr[u].l = l;
this.tr[u].r = r;
if (l === r) return;
const mid = (l + r) >> 1;
this.build(u << 1, l, mid);
this.build((u << 1) | 1, mid + 1, r);
}
modify(u: number, x: number, v: number): void {
if (this.tr[u].l === x && this.tr[u].r === x) {
this.tr[u].v += v;
return;
}
const mid = (this.tr[u].l + this.tr[u].r) >> 1;
if (x <= mid) {
this.modify(u << 1, x, v);
} else {
this.modify((u << 1) | 1, x, v);
}
this.pushup(u);
}
private pushup(u: number): void {
this.tr[u].v = this.tr[u << 1].v + this.tr[(u << 1) | 1].v;
}
query(u: number, l: number, r: number): number {
if (this.tr[u].l >= l && this.tr[u].r <= r) {
return this.tr[u].v;
}
const mid = (this.tr[u].l + this.tr[u].r) >> 1;
let res = 0;
if (l <= mid) {
res += this.query(u << 1, l, r);
}
if (r > mid) {
res += this.query((u << 1) | 1, l, r);
}
return res;
}
}
function goodTriplets(nums1: number[], nums2: number[]): number {
const n = nums1.length;
const pos = new Map<number, number>();
nums2.forEach((v, i) => pos.set(v, i + 1));
const tree = new SegmentTree(n);
let ans = 0;
for (const num of nums1) {
const p = pos.get(num)!;
const left = tree.query(1, 1, p);
const total = tree.query(1, 1, n);
const right = n - p - (total - left);
ans += left * right;
tree.modify(1, p, 1);
}
return ans;
}type Node struct {
l, r, v int
}
type SegmentTree struct {
tr []Node
}
func NewSegmentTree(n int) *SegmentTree {
tr := make([]Node, 4*n)
st := &SegmentTree{tr: tr}
st.build(1, 1, n)
return st
}
func (st *SegmentTree) build(u, l, r int) {
st.tr[u].l = l
st.tr[u].r = r
if l == r {
return
}
mid := (l + r) >> 1
st.build(u<<1, l, mid)
st.build(u<<1|1, mid+1, r)
}
func (st *SegmentTree) modify(u, x, v int) {
if st.tr[u].l == x && st.tr[u].r == x {
st.tr[u].v += v
return
}
mid := (st.tr[u].l + st.tr[u].r) >> 1
if x <= mid {
st.modify(u<<1, x, v)
} else {
st.modify(u<<1|1, x, v)
}
st.pushup(u)
}
func (st *SegmentTree) pushup(u int) {
st.tr[u].v = st.tr[u<<1].v + st.tr[u<<1|1].v
}
func (st *SegmentTree) query(u, l, r int) int {
if st.tr[u].l >= l && st.tr[u].r <= r {
return st.tr[u].v
}
mid := (st.tr[u].l + st.tr[u].r) >> 1
res := 0
if l <= mid {
res += st.query(u<<1, l, r)
}
if r > mid {
res += st.query(u<<1|1, l, r)
}
return res
}
func goodTriplets(nums1 []int, nums2 []int) int64 {
n := len(nums1)
pos := make(map[int]int)
for i, v := range nums2 {
pos[v] = i + 1
}
tree := NewSegmentTree(n)
var ans int64
for _, num := range nums1 {
p := pos[num]
left := tree.query(1, 1, p)
right := n - p - (tree.query(1, 1, n) - tree.query(1, 1, p))
ans += int64(left * right)
tree.modify(1, p, 1)
}
return ans
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), Space Complexity: O(1) |
| Optimized Approach Using Relative Position Arrays | Time Complexity: O(n^2), Space Complexity: O(n) |
| Binary Indexed Tree (Fenwick Tree) | – |
| Segment Tree | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Triplet Check | O(n^3) | O(1) | Small inputs or when demonstrating the basic definition of a good triplet |
| Relative Position Array + Binary Indexed Tree | O(n log n) | O(n) | General case; efficient for large permutations and common interview solution |
| Merge Sort / Divide and Conquer Counting | O(n log n) | O(n) | Alternative when using merge-based counting techniques for ordered triplets |
Frequently asked questions
Is Count Good Triplets in an Array easy or hard?
LeetCode classifies this problem as Hard because it requires recognizing a permutation mapping trick and applying advanced data structures like Binary Indexed Trees or segment trees. The underlying idea is counting increasing triplets efficiently rather than brute force enumeration.
Count Good Triplets in an Array Python/Java solution
Python, Java, C++, and other languages implement the same idea: convert nums1 into a position array based on nums2 and use a Binary Indexed Tree to count smaller elements to the left and larger elements to the right. Each update and query takes O(log n), giving an overall O(n log n) runtime.
How to solve Count Good Triplets in an Array in O(n log n)?
First map each value in nums2 to its index. Replace every element in nums1 with its corresponding index from nums2, producing a position array. Then iterate through this array and use a Binary Indexed Tree to count how many smaller elements appear before the current index and how many larger elements appear after it. Multiply the two counts to accumulate the number of good triplets.
What is the best approach for Count Good Triplets in an Array?
The most efficient approach maps values from nums1 to their positions in nums2, converting the task into counting increasing triplets in a single array. A Binary Indexed Tree (Fenwick Tree) then tracks how many smaller elements appear on the left and larger elements on the right. This solution runs in O(n log n) time and O(n) space.
Is Count Good Triplets in an Array asked at Google/Amazon/Meta?
Problems involving Binary Indexed Trees, segment trees, and counting ordered subsequences appear frequently in interviews at companies like Google, Amazon, and Meta. This specific problem tests permutation mapping and advanced data structure usage, making it common in high-level algorithm rounds.
What data structure is used in Count Good Triplets in an Array?
The optimized solution typically uses a Binary Indexed Tree (Fenwick Tree) to maintain prefix frequency counts while scanning the array. Segment Trees or ordered sets can also solve the same counting task with similar O(n log n) complexity.
What is the time complexity of Count Good Triplets in an Array?
The brute force approach checks all triplets and runs in O(n^3) time. The optimized solution uses a relative position array and a Binary Indexed Tree to count valid middle elements efficiently, reducing the complexity to O(n log n) with O(n) extra space.