2179. Count Good Triplets in an Array LeetCode Solution

Last updated: February 26, 2025

In this guide, you will get 2179. Count Good Triplets in an Array LeetCode Solution with the best time and space complexity. The solution to Count Good Triplets in an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Count Good Triplets in an Array solution in C++
Count Good Triplets in an Array solution in Java
Count Good Triplets in an Array solution in Python
Additional Resources

2179. Count Good Triplets in an Array LeetCode Solution image

Problem Statement of 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].

Complexity Analysis

Time Complexity: O(n\log n)
Space Complexity: O(n)

2179. Count Good Triplets in an Array LeetCode Solution in C++

class FenwickTree {
 public:
  FenwickTree(int n) : sums(n + 1) {}

  void add(int i, int delta) {
    while (i < sums.size()) {
      sums[i] += delta;
      i += lowbit(i);
    }
  }

  int get(int i) const {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

 private:
  vector<int> sums;

  static inline int lowbit(int i) {
    return i & -i;
  }
};

class Solution {
 public:
  long long goodTriplets(vector<int>& nums1, vector<int>& nums2) {
    const int n = nums1.size();
    long ans = 0;
    unordered_map<int, int> numToIndex;
    vector<int> arr;
    // leftSmaller[i] := the number of arr[j] < arr[i], where 0 <= j < i
    vector<int> leftSmaller(n);
    // rightLarger[i] := the number of arr[j] > arr[i], where i < j < n
    vector<int> rightLarger(n);
    FenwickTree tree1(n);  // Calculates `leftSmaller`.
    FenwickTree tree2(n);  // Calculates `rightLarger`.

    for (int i = 0; i < n; ++i)
      numToIndex[nums1[i]] = i;

    // Remap each number in `nums2` to the according index in `nums1` as `arr`.
    // So the problem is to find the number of increasing tripets in `arr`.
    for (const int num : nums2)
      arr.push_back(numToIndex[num]);

    for (int i = 0; i < n; ++i) {
      leftSmaller[i] = tree1.get(arr[i]);
      tree1.add(arr[i] + 1, 1);
    }

    for (int i = n - 1; i >= 0; --i) {
      rightLarger[i] = tree2.get(n) - tree2.get(arr[i]);
      tree2.add(arr[i] + 1, 1);
    }

    for (int i = 0; i < n; ++i)
      ans += static_cast<long>(leftSmaller[i]) * rightLarger[i];

    return ans;
  }
};
/* code provided by PROGIEZ */

2179. Count Good Triplets in an Array LeetCode Solution in Java

class FenwickTree {
  public FenwickTree(int n) {
    sums = new int[n + 1];
  }

  public void add(int i, int delta) {
    while (i < sums.length) {
      sums[i] += delta;
      i += lowbit(i);
    }
  }

  public int get(int i) {
    int sum = 0;
    while (i > 0) {
      sum += sums[i];
      i -= lowbit(i);
    }
    return sum;
  }

  private int[] sums;

  private static int lowbit(int i) {
    return i & -i;
  }
}

class Solution {
  public long goodTriplets(int[] nums1, int[] nums2) {
    final int n = nums1.length;
    long ans = 0;
    Map<Integer, Integer> numToIndex = new HashMap<>();
    int[] arr = new int[n];
    // leftSmaller[i] := the number of arr[j] < arr[i], where 0 <= j < i
    int[] leftSmaller = new int[n];
    // rightLarger[i] := the number of arr[j] > arr[i], where i < j < n
    int[] rightLarger = new int[n];
    FenwickTree tree1 = new FenwickTree(n); // Calculates `leftSmaller`.
    FenwickTree tree2 = new FenwickTree(n); // Calculates `rightLarger`.

    for (int i = 0; i < n; ++i)
      numToIndex.put(nums1[i], i);

    // Remap each number in `nums2` to the according index in `nums1` as `arr`.
    // So the problem is to find the number of increasing tripets in `arr`.
    for (int i = 0; i < n; ++i)
      arr[i] = numToIndex.get(nums2[i]);

    for (int i = 0; i < n; ++i) {
      leftSmaller[i] = tree1.get(arr[i]);
      tree1.add(arr[i] + 1, 1);
    }

    for (int i = n - 1; i >= 0; --i) {
      rightLarger[i] = tree2.get(n) - tree2.get(arr[i]);
      tree2.add(arr[i] + 1, 1);
    }

    for (int i = 0; i < n; ++i)
      ans += (long) leftSmaller[i] * rightLarger[i];

    return ans;
  }
}
// code provided by PROGIEZ

2179. Count Good Triplets in an Array LeetCode Solution in Python

class FenwickTree:
  def __init__(self, n: int):
    self.sums = [0] * (n + 1)

  def add(self, i: int, delta: int) -> None:
    while i < len(self.sums):
      self.sums[i] += delta
      i += FenwickTree.lowbit(i)

  def get(self, i: int) -> int:
    summ = 0
    while i > 0:
      summ += self.sums[i]
      i -= FenwickTree.lowbit(i)
    return summ

  @staticmethod
  def lowbit(i: int) -> int:
    return i & -i


class Solution:
  def goodTriplets(self, nums1: list[int], nums2: list[int]) -> int:
    n = len(nums1)
    numToIndex = {num: i for i, num in enumerate(nums1)}
    # Remap each number in `nums2` to the according index in `nums1` as `arr`.
    # So the problem is to find the number of increasing tripets in `arr`.
    arr = [numToIndex[num] for num in nums2]
    # leftSmaller[i] := the number of arr[j] < arr[i], where 0 <= j < i
    leftSmaller = [0] * n
    # rightLarger[i] := the number of arr[j] > arr[i], where i < j < n
    rightLarger = [0] * n
    tree1 = FenwickTree(n)  # Calculates `leftSmaller`.
    tree2 = FenwickTree(n)  # Calculates `rightLarger`.

    for i, a in enumerate(arr):
      leftSmaller[i] = tree1.get(a)
      tree1.add(a + 1, 1)

    for i, a in reversed(list(enumerate(arr))):
      rightLarger[i] = tree2.get(n) - tree2.get(a)
      tree2.add(a + 1, 1)

    return sum(a * b for a, b in zip(leftSmaller, rightLarger))
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents