2179. Count Good Triplets in an Array

Description

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].

 

Solutions

Solution: Binary Indexed Tree

• Time complexity: O(nlogn)
• Space complexity: O(n)

 

JavaScript

/**
 * @param {number[]} nums1
 * @param {number[]} nums2
 * @return {number}
 */
const goodTriplets = function (nums1, nums2) {
  const n = nums1.length;
  const num1Indexed = Array.from({ length: n }, () => -1);
  const leftTree = new BinaryIndexedTree(n);
  const rightTree = new BinaryIndexedTree(n);
  const leftCounts = Array.from({ length: n + 1 }, () => 0);
  const rightCounts = Array.from({ length: n + 1 }, () => 0);

  for (let index = 0; index < n; index++) {
    const num = nums1[index];

    num1Indexed[num] = index;
  }

  for (let index = 0; index < n; index++) {
    const num = nums2[index];
    const num1Index = num1Indexed[num];

    leftCounts[index] = leftTree.get(num1Index);
    leftTree.add(num1Index + 1, 1);
  }

  for (let index = n - 1; index >= 0; index--) {
    const num = nums2[index];
    const num1Index = num1Indexed[num];

    rightCounts[index] = rightTree.get(n) - rightTree.get(num1Index);
    rightTree.add(num1Index + 1, 1);
  }

  return leftCounts.reduce((result, count, index) => result + count * rightCounts[index], 0);
};

class BinaryIndexedTree {
  constructor(n) {
    this.sums = Array.from({ length: n + 1 }, () => 0);
  }

  add(index, delta) {
    while (index < this.sums.length) {
      this.sums[index] += delta;
      index += index & -index;
    }
  }

  get(index) {
    let sum = 0;

    while (index > 0) {
      sum += this.sums[index];
      index -= index & -index;
    }

    return sum;
  }
}