2179.js

/** ------------------------------------------------------------------------------
 * 
 * 2179. Count Good Triplets in an Array
 * Topics: Binary Indexed Tree, Segment Tree
 * https://leetcode.com/problems/count-good-triplets-in-an-array/?envType=daily-question&envId=2025-04-15
 * 
 ------------------------------------------------------------------------------ */
class FenwickTree {
  constructor(size) {
    this.tree = Array.from({ length: size + 1 }).fill(0)
  }

  update(index, delta) {
    index++
    while (index < this.tree.length) {
      this.tree[index] += delta
      index += index & -index
    }
  }

  query(index) {
    index++
    let res = 0
    while (index > 0) {
      res += this.tree[index]
      index -= index & -index
    }
    return res
  }
}

var goodTriplets = function (nums1, nums2) {
  const n = nums1.length
  const pos2 = Array(n),
    reversedIndexMapping = Array(n)
  for (let i = 0; i < n; i++) {
    pos2[nums2[i]] = i
  }
  for (let i = 0; i < n; i++) {
    reversedIndexMapping[pos2[nums1[i]]] = i
  }
  const tree = new FenwickTree(n)
  let res = 0
  for (let value = 0; value < n; value++) {
    const pos = reversedIndexMapping[value]
    const left = tree.query(pos)
    tree.update(pos, 1)
    const right = n - 1 - pos - (value - left)
    res += left * right
  }
  return res
}

console.log(goodTriplets([2, 0, 1, 3], [0, 1, 2, 3]))