2179. Count Good Triplets in an Array

[mah-shamim]

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

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 pos1_x < pos1_y < pos1_z. 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 pos2_x < pos2_y < pos2_z. 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.length
• 3 <= n <= 105
• 0 <= nums1[i], nums2[i] <= n - 1
• nums1 and nums2 are permutations of [0, 1, ..., n - 1].

Hint:

1. For every value y, how can you find the number of values x (0 ≤ x, y ≤ n - 1) such that x appears before y in both of the arrays?
2. Similarly, for every value y, try finding the number of values z (0 ≤ y, z ≤ n - 1) such that z appears after y in both of the arrays.
3. Now, for every value y, count the number of good triplets that can be formed if y is considered as the middle element.

[mah-shamim]

We need to count the number of good triplets (x, y, z) in two permutations such that the positions of x, y, and z are in increasing order in both permutations. A good triplet (x, y, z) must satisfy pos1[x] < pos1[y] < pos1[z] and pos2[x] < pos2[y] < pos2[z].

Approach

1. Precompute Positions: For each value in the permutations, compute its position in both arrays.
2. Element Structure: Create elements with their positions in both arrays.
3. Left Count Calculation: For each element y, compute how many elements x exist such that x appears before y in both arrays. This is done using a Fenwick Tree (Binary Indexed Tree) to efficiently count elements with smaller positions.
4. Right Count Calculation: For each element y, compute how many elements z exist such that z appears after y in both arrays. This is done using another Fenwick Tree in reverse order.
5. Combine Results: For each element y, the number of good triplets where y is the middle element is the product of left and right counts. Sum these products to get the total number of good triplets.

Let's implement this solution in PHP: 2179. Count Good Triplets in an Array

<?php
class FenwickTree {
    private $tree;
    private $size;

    /**
     * @param $size
     */
    public function __construct($size) {
        $this->size = $size;
        $this->tree = array_fill(0, $size + 1, 0); // 1-based indexing
    }

    /**
     * @param $index
     * @param $delta
     * @return void
     */
    public function update($index, $delta) {
        $index++; // convert to 1-based index
        while ($index <= $this->size) {
            $this->tree[$index] += $delta;
            $index += $index & -$index;
        }
    }

    /**
     * @param $index
     * @return int|mixed
     */
    public function query($index) {
        $index++; // convert to 1-based index
        $sum = 0;
        while ($index > 0) {
            $sum += $this->tree[$index];
            $index -= $index & -$index;
        }
        return $sum;
    }
}

/**
 * @param Integer[] $nums1
 * @param Integer[] $nums2
 * @return Integer
 */
function goodTriplets($nums1, $nums2) {
    $n = count($nums1);
    $pos1 = array();
    $pos2 = array();
    for ($i = 0; $i < $n; $i++) {
        $pos1[$nums1[$i]] = $i;
        $pos2[$nums2[$i]] = $i;
    }
    $elements = array();
    for ($x = 0; $x < $n; $x++) {
        $elements[] = array('x' => $x, 'a' => $pos1[$x], 'b' => $pos2[$x]);
    }

    // Compute left counts
    usort($elements, function($a, $b) {
        return $a['a'] - $b['a'];
    });
    $ft_left = new FenwickTree($n);
    $left = array_fill(0, $n, 0);
    foreach ($elements as $elem) {
        $x = $elem['x'];
        $b = $elem['b'];
        $left[$x] = $ft_left->query($b - 1);
        $ft_left->update($b, 1);
    }

    // Compute right counts
    usort($elements, function($a, $b) {
        return $b['a'] - $a['a'];
    });
    $ft_right = new FenwickTree($n);
    $right = array_fill(0, $n, 0);
    $total = 0;
    foreach ($elements as $elem) {
        $x = $elem['x'];
        $b = $elem['b'];
        $sum = $ft_right->query($b);
        $right[$x] = $total - $sum;
        $ft_right->update($b, 1);
        $total++;
    }

    // Calculate result
    $result = 0;
    for ($x = 0; $x < $n; $x++) {
        $result += $left[$x] * $right[$x];
    }
    return $result;
}

// Example 1
$nums1 = [2, 0, 1, 3];
$nums2 = [0, 1, 2, 3];
echo countGoodTriplets($nums1, $nums2) . "\n"; // Output: 1

// Example 2
$nums1 = [4, 0, 1, 3, 2];
$nums2 = [4, 1, 0, 2, 3];
echo countGoodTriplets($nums1, $nums2) . "\n"; // Output: 4
?>

Explanation:

1. Fenwick Tree: This data structure is used to efficiently compute prefix sums and update counts, which allows us to determine how many elements have positions less than or greater than a given element in logarithmic time.
2. Left Count Calculation: By sorting elements based on their positions in the first array, we use a Fenwick Tree to count how many elements have smaller positions in the second array.
3. Right Count Calculation: Similarly, by sorting elements in reverse order and using another Fenwick Tree, we count how many elements have larger positions in the second array.
4. Combining Results: For each element, the product of its left and right counts gives the number of good triplets where it is the middle element. Summing these products gives the total number of good triplets.

This approach ensures that we efficiently count the required elements using Fenwick Trees, resulting in an overall time complexity of O(n log n), which is suitable for large input sizes up to 100,000.

[basharul-siddike]

Thanks for solving the problem of "Count Good Triplets in an Array"

[mah-shamim]

Thanks