Count good triplets in an array

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

65.8% acceptance

Feb 25, 2026

1011

114

You are given two 0-indexed arrays nums1 and nums2 of length n, both permutations of [0..n-1]. A good triplet is a set of 3 distinct values (x, y, z) with positions increasing in both nums1 and nums2. Return the total number of good triplets.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn good_triplets(nums1: Vec<i32>, nums2: Vec<i32>) -> i64 {
    let n = nums1.len();
    let mut pos2 = vec![0usize; n];
    for (i, &v) in nums2.iter().enumerate() {
      pos2[v as usize] = i;
    }

    // Fenwick tree (BIT) for counting
    let mut bit = vec![0i64; n + 1];

    let bit_update = |bit: &mut Vec<i64>, mut i: usize| {
      i += 1;
      while i <= n {
        bit[i] += 1;
        i += i & i.wrapping_neg();
      }
    };
    let bit_query = |bit: &Vec<i64>, mut i: usize| -> i64 {
      // sum of positions 0..i-1 (0-indexed) = prefix sum of 1..i (1-indexed)
      let mut s = 0i64;
      while i > 0 {
        s += bit[i];
        i -= i & i.wrapping_neg();
      }
      s
    };

    let mut ans = 0i64;
    for (i, &val) in nums1.iter().enumerate() {
      let p = pos2[val as usize];
      // left = count of already-processed values with pos2 < p
      let left = bit_query(&bit, p);
      // right = count of not-yet-processed values with pos2 > p
      let right = (n - 1 - p) as i64 - (i as i64 - left);
      ans += left * right;
      bit_update(&mut bit, p);
    }
    ans
  }
}