LeetCode 2179 - Count Good Triplets in an Array

LeetCode Problem 2179

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Divide and Conquer, Binary Indexed Tree, Segment Tree, Merge Sort, Ordered Set

Solution

Problem Understanding

In this problem, we are given two arrays, nums1 and nums2, each containing every integer from 0 to n - 1 exactly once. In other words, both arrays are permutations of the same set of values.

We need to count how many triplets (x, y, z) satisfy an ordering condition in both arrays simultaneously.

For a triplet to be considered "good", the following must hold:

• In nums1, the position of x must come before y, and the position of y must come before z
• In nums2, the same ordering must also hold

Formally:

• pos1[x] < pos1[y] < pos1[z]
• pos2[x] < pos2[y] < pos2[z]

The important detail is that the triplet consists of values, not indices. We are comparing where those values appear inside the two arrays.

The constraints are large:

• n can be as large as 100000
• A brute force enumeration of all triplets would require checking approximately n^3 combinations

Since 100000^3 is astronomically large, any cubic or even quadratic solution is too slow. This strongly suggests that we need an efficient counting technique using advanced data structures such as:

• Binary Indexed Tree
• Segment Tree
• Ordered statistics
• Merge sort counting

Another important observation is that both arrays are permutations. This means every value appears exactly once in each array. Because of this, we can map values from one array into positions in the other array, transforming the problem into an order counting problem on a single array.

Some edge cases that matter:

• Arrays that are already in the same order, every increasing triplet is valid
• Arrays in nearly opposite order, very few or zero triplets exist
• Smallest valid input size n = 3
• Large inputs where performance becomes critical
• Cases where one middle element has many valid left elements but few right elements, or vice versa

The permutation guarantee simplifies many implementation details because we never need to handle duplicates.

Approaches

Brute Force

The most direct approach is to enumerate every possible triplet (x, y, z) and verify whether it appears in increasing order in both arrays.

We can first build two position maps:

• pos1[value] = index in nums1
• pos2[value] = index in nums2

Then for every combination of three distinct values, we check:

pos1[x] < pos1[y] < pos1[z]
and
pos2[x] < pos2[y] < pos2[z]

If both conditions hold, we increment the answer.

This works because it directly follows the problem definition. However, there are O(n^3) triplets, which is completely infeasible for n = 100000.

Key Insight

The important observation is that we only care about relative ordering.

Suppose we map every value in nums1 to its position in nums2.

Example:

nums1 = [2,0,1,3]
nums2 = [0,1,2,3]

Positions in nums2:

0 -> 0
1 -> 1
2 -> 2
3 -> 3

Transform nums1:

[2,0,1,3]
 ->
[2,0,1,3]

Now the problem becomes:

Count increasing subsequences of length 3 in this transformed array.

Why does this work?

• The order in nums1 is already fixed by iterating through the transformed array
• If indices in the transformed array are increasing, then the corresponding values also appear in increasing order in nums2

Now we can process each element as the middle element of a triplet:

• Count how many smaller elements exist to its left
• Count how many larger elements exist to its right
• Multiply the two counts

This can be done efficiently with a Binary Indexed Tree in O(n log n) time.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n³)	O(n)	Checks every triplet explicitly
Optimal	O(n log n)	O(n)	Uses permutation mapping and Binary Indexed Tree

Algorithm Walkthrough

Step 1: Build Position Mapping

Create an array position_in_nums2 where:

position_in_nums2[value] = index of value in nums2

This allows us to instantly determine where each value appears in nums2.

For example:

nums2 = [4,1,0,2,3]

position_in_nums2:
0 -> 2
1 -> 1
2 -> 3
3 -> 4
4 -> 0

Step 2: Transform nums1

Replace every value in nums1 with its position in nums2.

Example:

nums1 = [4,0,1,3,2]

transformed:
[0,2,1,4,3]

Now the problem becomes:

Count increasing subsequences of length 3 in this transformed array.

Why?

Because:

• The index order in the transformed array already represents order in nums1
• Increasing values inside the transformed array represent increasing order in nums2

Step 3: Count Smaller Elements on the Left

We process the transformed array from left to right.

For each position i, we want:

left_smaller[i]
=
number of previous elements smaller than transformed[i]

We use a Binary Indexed Tree to maintain frequencies of previously seen values.

For each value:

1. Query how many smaller values have appeared
2. Store the result
3. Insert the current value into the BIT

The Binary Indexed Tree supports:

• Prefix sum query in O(log n)
• Point update in O(log n)

Step 4: Count Larger Elements on the Right

Now process from right to left.

For each position i, we want:

right_larger[i]
=
number of later elements larger than transformed[i]

Again use a Binary Indexed Tree.

At each step:

1. Query how many elements already inserted are larger
2. Store the result
3. Insert current value

Step 5: Combine Counts

Treat every position as the middle element of a triplet.

If:

• left_smaller[i] = a
• right_larger[i] = b

then there are:

a * b

good triplets centered at position i.

Sum over all positions.

Why it works

After transformation, the array represents the order of elements in nums2 while preserving the order from nums1.

An increasing subsequence of length 3 in the transformed array corresponds exactly to three values that appear in increasing order in both arrays.

For each middle element:

• Any valid left element must be smaller
• Any valid right element must be larger

Every pair of such choices forms a unique valid triplet, so multiplying the counts gives the exact number of triplets centered at that position.

Python Solution

from typing import List

class BIT:
    def __init__(self, size: int):
        self.size = size
        self.tree = [0] * (size + 1)

    def update(self, index: int, delta: int) -> None:
        index += 1

        while index <= self.size:
            self.tree[index] += delta
            index += index & -index

    def query(self, index: int) -> int:
        index += 1
        result = 0

        while index > 0:
            result += self.tree[index]
            index -= index & -index

        return result

class Solution:
    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)

        position_in_nums2 = [0] * n

        for index, value in enumerate(nums2):
            position_in_nums2[value] = index

        transformed = [position_in_nums2[value] for value in nums1]

        left_smaller = [0] * n
        bit = BIT(n)

        for i in range(n):
            value = transformed[i]

            left_smaller[i] = bit.query(value - 1)
            bit.update(value, 1)

        right_larger = [0] * n
        bit = BIT(n)

        for i in range(n - 1, -1, -1):
            value = transformed[i]

            total_seen = bit.query(n - 1)
            smaller_or_equal = bit.query(value)

            right_larger[i] = total_seen - smaller_or_equal

            bit.update(value, 1)

        answer = 0

        for i in range(n):
            answer += left_smaller[i] * right_larger[i]

        return answer

The implementation starts by constructing a position lookup table for nums2. Since both arrays are permutations, every value has exactly one position.

Next, the code transforms nums1 into an array of positions inside nums2. This reduces the original problem into counting increasing subsequences of length 3.

The BIT class implements a Binary Indexed Tree, also known as a Fenwick Tree. It supports efficient prefix sum queries and point updates in logarithmic time.

The first pass computes left_smaller. For each element, the BIT stores all previously seen values. Querying value - 1 tells us how many smaller elements appear before the current element.

The second pass computes right_larger. We traverse from right to left and maintain another BIT containing elements already seen on the right side. The difference:

total_seen - smaller_or_equal

gives the number of strictly larger elements to the right.

Finally, each index is treated as the middle element of a triplet. Multiplying the number of valid left choices and right choices gives the total contribution for that position.

Go Solution

package main

type BIT struct {
	tree []int
	size int
}

func NewBIT(size int) *BIT {
	return &BIT{
		tree: make([]int, size+1),
		size: size,
	}
}

func (b *BIT) Update(index int, delta int) {
	index++

	for index <= b.size {
		b.tree[index] += delta
		index += index & -index
	}
}

func (b *BIT) Query(index int) int {
	index++

	result := 0

	for index > 0 {
		result += b.tree[index]
		index -= index & -index
	}

	return result
}

func goodTriplets(nums1 []int, nums2 []int) int64 {
	n := len(nums1)

	positionInNums2 := make([]int, n)

	for index, value := range nums2 {
		positionInNums2[value] = index
	}

	transformed := make([]int, n)

	for i, value := range nums1 {
		transformed[i] = positionInNums2[value]
	}

	leftSmaller := make([]int, n)
	bit := NewBIT(n)

	for i := 0; i < n; i++ {
		value := transformed[i]

		leftSmaller[i] = bit.Query(value - 1)
		bit.Update(value, 1)
	}

	rightLarger := make([]int, n)
	bit = NewBIT(n)

	for i := n - 1; i >= 0; i-- {
		value := transformed[i]

		totalSeen := bit.Query(n - 1)
		smallerOrEqual := bit.Query(value)

		rightLarger[i] = totalSeen - smallerOrEqual

		bit.Update(value, 1)
	}

	var answer int64 = 0

	for i := 0; i < n; i++ {
		answer += int64(leftSmaller[i] * rightLarger[i])
	}

	return answer
}

The Go implementation follows the same algorithmic structure as the Python version.

One important difference is the return type. The problem requires returning int64 because the number of triplets can exceed the range of a 32-bit integer.

The Binary Indexed Tree is implemented as a struct with methods for updates and prefix queries. Go slices are used instead of Python lists, but the logic remains identical.

Another detail is explicit integer conversion when accumulating the final answer:

answer += int64(leftSmaller[i] * rightLarger[i])

Without this conversion, integer overflow could occur on some platforms.

Worked Examples

Example 1

nums1 = [2,0,1,3]
nums2 = [0,1,2,3]

Step 1: Build Position Map

Value	Position in nums2
0	0
1	1
2	2
3	3

Step 2: Transform nums1

nums1:
[2,0,1,3]

transformed:
[2,0,1,3]

Step 3: Compute left_smaller

i	value	smaller on left	left_smaller
0	2	0	0
1	0	0	0
2	1	1	1
3	3	3	3

Result:

left_smaller = [0,0,1,3]

Step 4: Compute right_larger

i	value	larger on right	right_larger
3	3	0	0
2	1	1	1
1	0	2	2
0	2	1	1

Result:

right_larger = [1,2,1,0]

Step 5: Combine

i	left_smaller	right_larger	contribution
0	0	1	0
1	0	2	0
2	1	1	1
3	3	0	0

Total:

1

Example 2

nums1 = [4,0,1,3,2]
nums2 = [4,1,0,2,3]

Position Map

Value	Position
0	2
1	1
2	3
3	4
4	0

Transformed Array

[0,2,1,4,3]

left_smaller

i	value	left_smaller
0	0	0
1	2	1
2	1	1
3	4	3
4	3	3

right_larger

i	value	right_larger
4	3	0
3	4	0
2	1	2
1	2	2
0	0	4

Contributions

i	left	right	contribution
0	0	4	0
1	1	2	2
2	1	2	2
3	3	0	0
4	3	0	0

Total:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Each BIT query and update takes O(log n), performed O(n) times
Space	O(n)	Position map, transformed array, BIT, and helper arrays

The Binary Indexed Tree supports both update and prefix sum operations in logarithmic time. Since we perform a constant number of these operations for every element, the overall runtime becomes O(n log n).

The auxiliary memory usage is linear because we store several arrays of size n.

Test Cases

from typing import List

class Solution:
    def goodTriplets(self, nums1: List[int], nums2: List[int]) -> int:
        n = len(nums1)

        pos = [0] * n

        for i, v in enumerate(nums2):
            pos[v] = i

        arr = [pos[v] for v in nums1]

        class BIT:
            def __init__(self, size):
                self.tree = [0] * (size + 1)
                self.size = size

            def update(self, index, delta):
                index += 1

                while index <= self.size:
                    self.tree[index] += delta
                    index += index & -index

            def query(self, index):
                index += 1
                result = 0

                while index > 0:
                    result += self.tree[index]
                    index -= index & -index

                return result

        left = [0] * n
        bit = BIT(n)

        for i, v in enumerate(arr):
            left[i] = bit.query(v - 1)
            bit.update(v, 1)

        right = [0] * n
        bit = BIT(n)

        for i in range(n - 1, -1, -1):
            v = arr[i]

            right[i] = bit.query(n - 1) - bit.query(v)
            bit.update(v, 1)

        answer = 0

        for i in range(n):
            answer += left[i] * right[i]

        return answer

solver = Solution()

assert solver.goodTriplets(
    [2,0,1,3],
    [0,1,2,3]
) == 1  # official example 1

assert solver.goodTriplets(
    [4,0,1,3,2],
    [4,1,0,2,3]
) == 4  # official example 2

assert solver.goodTriplets(
    [0,1,2],
    [0,1,2]
) == 1  # smallest size with one valid triplet

assert solver.goodTriplets(
    [0,1,2],
    [2,1,0]
) == 0  # completely reversed ordering

assert solver.goodTriplets(
    [0,1,2,3],
    [0,1,2,3]
) == 4  # every triplet is valid

assert solver.goodTriplets(
    [3,2,1,0],
    [0,1,2,3]
) == 0  # no increasing subsequence of length 3

assert solver.goodTriplets(
    [1,0,2,3],
    [0,1,2,3]
) == 2  # mixed ordering

assert solver.goodTriplets(
    [0,2,1,3],
    [0,1,2,3]
) == 2  # partial inversion

assert solver.goodTriplets(
    [2,1,0,3,4],
    [0,1,2,3,4]
) == 4  # only later elements form triplets

Test	Why
[2,0,1,3] and [0,1,2,3]	Verifies official example
[4,0,1,3,2] and [4,1,0,2,3]	Verifies official example
[0,1,2] and [0,1,2]	Smallest valid input with one triplet
[0,1,2] and [2,1,0]	No valid triplets
Identical sorted arrays	Every increasing triplet should count
Reverse ordering	Ensures algorithm handles zero answers correctly
Partial inversions	Verifies mixed ordering behavior
Larger mixed case	Stresses counting logic

Edge Cases

One important edge case occurs when both arrays are identical and strictly increasing. In this scenario, every possible combination of three indices forms a valid triplet. This can produce very large answers, especially for large n. The implementation handles this correctly because the Binary Indexed Tree efficiently counts all increasing subsequences, and the Go solution uses int64 to avoid overflow.

Another important case is when the arrays are effectively reversed relative to each other. For example:

nums1 = [0,1,2]
nums2 = [2,1,0]

In this situation, no increasing triplet can exist because every ordering in one array becomes decreasing in the other. The implementation naturally handles this because the transformed array contains no increasing subsequences of length three, causing all contributions to become zero.

A subtle edge case involves middle elements that have many smaller values on the left but no larger values on the right, or vice versa. Since the algorithm multiplies the two counts, any missing side correctly produces zero contribution. This prevents invalid partial triplets from being counted.

Another potential source of bugs is off by one indexing inside the Binary Indexed Tree. The implementation carefully converts zero based array indices into one based BIT indices internally by incrementing the index before updates and queries. This ensures prefix sums are computed correctly for all values from 0 to n - 1.