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 wo

goodTriplets.js

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
// Class for Binary Indexed Tree (BIT), also known as Fenwick Tree
class BIT {
    constructor(size) {
        this.n = size; // Size of the BIT
        this.tree = new Array(size + 1).fill(0); // Initialize BIT array with zeros (1-based index)
    }

    // Update BIT at index i with a value val
    update(i, val) {
        i++; // Convert to 1-based index
        while (i <= this.n) {
            this.tree[i] += val; // Add val to the current index
            i += i & -i; // Move to the next index using BIT logic
        }
    }

    // Query the cumulative sum up to index i
    query(i) {
        i++; // Convert to 1-based index
        let res = 0; // Initialize result
        while (i > 0) {
            res += this.tree[i]; // Add the value at the current index
            i -= i & -i; // Move to the parent index
        }
        return res; // Return the cumulative sum
    }
}

// Function to count good triplets
var goodTriplets = function(nums1, nums2) {
    const n = nums1.length;

    // Map the positions of elements in nums2 to their values
    const pos = new Array(n);
    for (let i = 0; i < n; i++) {
        pos[nums2[i]] = i; // Position mapping from nums2
    }

    // Replace the values in nums1 with their positions in nums2
    for (let i = 0; i < n; i++) {
        nums1[i] = pos[nums1[i]];
    }

    // Initialize two BIT instances
    const bit1 = new BIT(n); // Tracks cumulative counts of elements
    const bit2 = new BIT(n); // Tracks cumulative contributions to triplets

    let ans = 0; // Initialize the answer to store the count of good triplets

    // Traverse nums1 in reverse to build triplets dynamically
    for (let i = n - 1; i >= 0; i--) {
        const x = nums1[i]; // Position of the current element in nums2

        // Query BIT1 to get the count of elements after x
        const val = bit1.query(n - 1) - bit1.query(x);

        // Query BIT2 to get the count of good triplets that can be formed
        const trip = bit2.query(n - 1) - bit2.query(x);

        ans += trip; // Add the count of triplets to the result

        // Update BIT2 with val (contribution to triplets for future elements)
        bit2.update(x, val);

        // Update BIT1 to include the current element
        bit1.update(x, 1);
    }

    return ans; // Return the total number of good triplets
};