Count Good Triplets in an Array

Count Good Triplets in an Array

What is this problem about?

This "Hard" difficulty problem involves two permutations of the same set of numbers. A "good triplet" is a set of three values $(x, y, z)$ that appear in the same relative order in both arrays. For example, if both array A and array B show $x$ appearing before $y$, and $y$ appearing before $z$, then $(x, y, z)$ is a good triplet. The task is to calculate the total number of such triplets efficiently.

Why is this asked in interviews?

Google and Bloomberg use this problem to test a candidate's mastery of advanced data structures and coordinate transformation. It moves beyond simple array traversal and requires you to map the values of one array to their indices in the other. This transformation effectively turns the problem into finding "increasing triplets" or counting inversions, a classic high-level algorithmic challenge.

Algorithmic pattern used

The problem is typically solved using a Binary Indexed Tree (BIT) or a Segment Tree. By mapping the positions of elements in the first array to their corresponding positions in the second, the problem becomes: for each element at index $i$, how many elements to its left have a smaller mapped index, and how many to its right have a larger mapped index? Multiplying these two counts for each position gives the number of triplets centered at that position.

Example explanation

Imagine nums1 = [2, 0, 1] and nums2 = [0, 1, 2].

1. Map values to indices in nums2: $0 o 0, 1 o 1, 2 o 2$.
2. In nums1, replace values with these indices: nums1 becomes [2, 0, 1].
3. Now we count triplets $(i, j, k)$ in this new array where $i < j < k$ and $val[i] < val[j] < val[k]$.
   • At index 1 (value 0): No smaller values to the left.
   • At index 2 (value 1): One smaller value to the left (0 at index 1), but its index in nums1 is 1, which is not $1 < 2$... wait. Actually, you'd use the BIT to count how many smaller indices appeared before you. For value 1 in [2, 0, 1], only 0 appeared before it at a smaller index.

Common mistakes candidates make

A major pitfall is trying to solve this in $O(n^2)$ or $O(n^3)$ using nested loops, which will fail for large inputs (e.g., $n = 10^5$). Another mistake is incorrect coordinate mapping—getting the "pos" array backwards. Finally, failing to realize that the counts of smaller elements on the left and larger elements on the right must be multiplied is a frequent logical error.

Interview preparation tip

Mastering the Binary Indexed Tree (BIT) is essential for "Hard" array problems. It allows for $O(\log n)$ updates and queries, which is the key to reducing the complexity of counting problems from quadratic to $n \log n$.