{x}
blog image

Count Good Triplets in an Array

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

Solution Explanation for Counting Good Triplets

This problem asks to find the number of good triplets in two arrays, nums1 and nums2, which are permutations of [0, 1, ..., n-1]. A good triplet (x, y, z) satisfies two conditions:

  1. The indices of x, y, and z in nums1 are in increasing order: pos1<sub>x</sub> < pos1<sub>y</sub> < pos1<sub>z</sub>.
  2. The indices of x, y, and z in nums2 are also in increasing order: pos2<sub>x</sub> < pos2<sub>y</sub> < pos2<sub>z</sub>.

The most efficient solution uses a Binary Indexed Tree (BIT) or a Segment Tree. Both data structures allow for efficient querying of prefix sums and updates. Let's break down the solution using a BIT:

Algorithm using Binary Indexed Tree (BIT):

  1. Preprocessing: Create a map pos to store the index of each number in nums2. This allows for O(1) lookup of the position of a number.

  2. Iteration: Iterate through nums1. For each number num in nums1:

    • Get its position p in nums2 using the pos map.
    • Query the BIT: left = tree.query(p -1) gives the count of numbers in nums2 whose positions are strictly less than p. This represents the number of potential x values for our good triplet where pos2<sub>x</sub> < pos2<sub>num</sub>.
    • right = n - p - (tree.query(n) - tree.query(p)) calculates the count of numbers in nums2 whose positions are strictly greater than p. This represents the number of potential z values where pos2<sub>z</sub> > pos2<sub>num</sub>.
    • Update ans: Add the product left * right to ans. This represents all possible good triplets that include the current number num.
    • Update the BIT: tree.update(p, 1) increments the count at position p in the BIT.

  3. Return: Return ans, which is the total number of good triplets.

Time Complexity: O(n log n), where n is the length of the arrays. This is dominated by the BIT's query and update operations, which are both O(log n).

Space Complexity: O(n) to store the BIT and the pos map.

Code Explanation (Python):

The Python code implements the BIT class and the solution as described above. Note that the BIT uses 1-based indexing, so we add 1 to the indices obtained from nums2.

Other Solutions (Segment Tree):

A segment tree can also solve this problem with the same time and space complexity. The core idea is identical; we use the segment tree to efficiently query the number of elements with indices smaller and larger than the current element's index in nums2. The implementation will be slightly more complex due to the tree structure. The provided Java and C++ code snippets showcase segment tree-based solutions. The Go code, however, uses a BIT.

Choosing between BIT and Segment Tree:

For this specific problem, both BIT and segment tree provide the same asymptotic time complexity. The BIT is generally slightly faster in practice due to its simpler structure and lower constant factors. However, the Segment tree might be preferred if you need additional functionalities like range updates, which are not easily implemented with a BIT.