# Count Good Triplets
**Difficulty:** EASY
[External](https://leetcode.com/problems/count-good-triplets)
Canonical: https://scaleengineer.com/dsa/problems/count-good-triplets
**Patterns:** [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array
**Companies:** [Turvo](https://scaleengineer.com/companies/turvo)
---
## Problem
Given an array of integers `arr`, and three integers `a`, `b` and `c`. You need to find the number of good triplets.

A triplet `(arr[i], arr[j], arr[k])` is **good** if the following conditions are true:

* `0 <= i < j < k < arr.length`
* `|arr[i] - arr[j]| <= a`
* `|arr[j] - arr[k]| <= b`
* `|arr[i] - arr[k]| <= c`

Where `|x|` denotes the absolute value of `x`.

Return _the number of good triplets_.

**Example 1:**

**Input:** arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
**Output:** 4
**Explanation:** There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].

**Example 2:**

**Input:** arr = [1,1,2,2,3], a = 0, b = 0, c = 1
**Output:** 0
**Explanation:** No triplet satisfies all conditions.

**Constraints:**

* `3 <= arr.length <= 100`
* `0 <= arr[i] <= 1000`
* `0 <= a, b, c <= 1000`

# Approaches
## Brute-Force Triple Nested Loop
This is the most straightforward and intuitive approach. It involves using three nested loops to iterate through all possible triplets of indices `(i, j, k)` that satisfy the condition `0 <= i < j < k < arr.length`. For each valid triplet of indices, it checks if the corresponding values in the array satisfy the three absolute difference conditions. If all conditions are met, a counter is incremented.
**Time:** O(n^3), where `n` is the length of the array `arr`. This is because of the three nested loops that iterate through all possible triplets. · **Space:** O(1), as we only use a constant amount of extra space for the counter and loop variables.
**Pros:** Very simple to understand and implement.; Requires no additional space beyond a few variables for loops and counting.; For the given constraints (`n <= 100`), this approach is fast enough to pass.
**Cons:** The cubic time complexity makes this approach inefficient for larger input sizes (e.g., if `n` were greater than a few hundred).
### Explanation
The algorithm iterates through every possible combination of three distinct indices `i`, `j`, and `k` from the array, ensuring that `i < j < k`. This is achieved using three nested loops.

*   The outer loop picks the first element, `arr[i]`, iterating `i` from `0` to `n-3`.
*   The middle loop picks the second element, `arr[j]`, iterating `j` from `i+1` to `n-2`.
*   The inner loop picks the third element, `arr[k]`, iterating `k` from `j+1` to `n-1`.

Inside the innermost loop, we have a unique triplet `(arr[i], arr[j], arr[k])`. We then check if this triplet is "good" by verifying the three given conditions:
1.  `|arr[i] - arr[j]| <= a`
2.  `|arr[j] - arr[k]| <= b`
3.  `|arr[i] - arr[k]| <= c`

If all three conditions hold true, we increment a counter variable. After all possible triplets have been checked, the final value of the counter is the answer.

```java
class Solution {
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int n = arr.length;
        int count = 0;
        for (int i = 0; i < n - 2; i++) {
            for (int j = i + 1; j < n - 1; j++) {
                if (Math.abs(arr[i] - arr[j]) <= a) {
                    for (int k = j + 1; k < n; k++) {
                        if (Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
                            count++;
                        }
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
*   Initialize a counter `count` to 0.
*   Iterate through the array with a variable `i` from `0` to `length - 3`.
*   Inside this loop, iterate with a variable `j` from `i + 1` to `length - 2`.
*   Inside this second loop, check if `|arr[i] - arr[j]| <= a`. If not, you can continue to the next `j` to optimize slightly.
*   If the first condition holds, iterate with a variable `k` from `j + 1` to `length - 1`.
*   Check if the remaining two conditions, `|arr[j] - arr[k]| <= b` and `|arr[i] - arr[k]| <= c`, are met.
*   If all three conditions are met, increment `count`.
*   After the loops complete, return `count`.

## Optimized Approach using Fenwick Tree
This approach improves upon the brute-force method by using a Fenwick Tree (also known as a Binary Indexed Tree or BIT) to optimize the counting process. Instead of a third loop to find `k`, we can restructure the loops to fix `j` and `k` and then efficiently count the number of valid `i`'s. This reduces the time complexity from cubic to quadratic.
**Time:** O(n^2 * logV), where `n` is the length of the array and `V` is the range of values in the array. The two nested loops for `j` and `k` run in O(n^2), and each Fenwick Tree query takes O(logV) time. · **Space:** O(V), where `V` is the maximum possible value in the array (1001 in this case). This space is used for the Fenwick Tree.
**Pros:** More efficient than the brute-force approach, with a time complexity of O(n^2 * logV).; The space complexity of O(V) is efficient as it does not depend on the input size `n`.
**Cons:** More complex to understand and implement compared to the brute-force solution.; The overhead of the data structure might make it slightly slower than the brute-force approach for very small `n`, although its asymptotic complexity is better.
### Explanation
The core idea is to iterate through the middle index `j` and the last index `k` of the triplet, and for each pair `(j, k)`, efficiently count the number of valid first indices `i` (where `i < j`).

We loop `j` from `1` to `n-2`. For each `j`, we maintain a data structure that stores the frequencies of values in `arr[0...j-1]`. A Fenwick Tree is ideal for this as it allows for efficient updates and range sum queries. The values in `arr` are up to 1000, so the Fenwick Tree will be of size 1001.

As we iterate `j` from `1` to `n-2`, we do the following:
1.  Update the Fenwick Tree with `arr[j-1]`. Now the tree contains the frequency distribution of all elements with indices less than `j`.
2.  Start an inner loop for `k` from `j+1` to `n-1`.
3.  For the pair `(j, k)`, if `|arr[j] - arr[k]| <= b`, we need to count `i < j` such that `|arr[i] - arr[j]| <= a` and `|arr[i] - arr[k]| <= c`. These two conditions define a valid range for the value of `arr[i]`: `[max(arr[j]-a, arr[k]-c), min(arr[j]+a, arr[k]+c)]`.
4.  We query our Fenwick Tree for the number of elements in this calculated range. This query, which takes `O(log V)` time (where `V` is the maximum value), gives us the number of valid `i`'s for the current `j` and `k`.
5.  This count is added to our total result.

This method avoids the third linear scan, replacing it with a logarithmic time query, thus improving the overall time complexity.

```java
class FenwickTree {
    private int[] bit;
    private int size;

    public FenwickTree(int size) {
        this.size = size;
        this.bit = new int[size + 1];
    }

    public void update(int index, int delta) {
        index++; // 1-based index
        while (index <= size) {
            bit[index] += delta;
            index += index & -index;
        }
    }

    public int query(int index) {
        if (index < 0) return 0;
        index++; // 1-based index
        int sum = 0;
        while (index > 0) {
            sum += bit[index];
            index -= index & -index;
        }
        return sum;
    }
    
    public int queryRange(int left, int right) {
        if (left > right) {
            return 0;
        }
        return query(right) - query(left - 1);
    }
}

class Solution {
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int n = arr.length;
        if (n < 3) return 0;
        
        int count = 0;
        int maxValue = 1000;
        
        FenwickTree ft = new FenwickTree(maxValue + 1);
        
        // ft will store counts of elements arr[0...j-1]
        for (int j = 1; j < n - 1; j++) {
            // Update ft with arr[j-1] to include it in the counts for i < j
            ft.update(arr[j-1], 1);
            
            for (int k = j + 1; k < n; k++) {
                if (Math.abs(arr[j] - arr[k]) <= b) {
                    // Count i < j such that:
                    // |arr[i] - arr[j]| <= a  => arr[j]-a <= arr[i] <= arr[j]+a
                    // |arr[i] - arr[k]| <= c  => arr[k]-c <= arr[i] <= arr[k]+c
                    int low = Math.max(arr[j] - a, arr[k] - c);
                    int high = Math.min(arr[j] + a, arr[k] + c);
                    
                    low = Math.max(0, low);
                    high = Math.min(maxValue, high);
                    
                    count += ft.queryRange(low, high);
                }
            }
        }
        
        return count;
    }
}
```
### Algorithm
*   Initialize `count = 0` and a Fenwick Tree `ft` of size `maxValue + 1` (where `maxValue` is 1000).
*   Iterate `j` from `1` to `n-2` (where `n` is the array length).
*   Before the inner loop for `k`, update the Fenwick Tree with the element at `j-1`: `ft.update(arr[j-1], 1)`. This makes the frequency counts of elements at indices less than `j` available for querying.
*   Start an inner loop for `k` from `j+1` to `n-1`.
*   Inside the `k` loop, first check if `|arr[j] - arr[k]| <= b`.
*   If it's true, calculate the valid range `[low, high]` for `arr[i]` based on `arr[j]`, `arr[k]`, `a`, and `c`.
*   Query the Fenwick Tree for the number of elements in this range: `ft.queryRange(low, high)`.
*   Add the result of the query to the total `count`.
*   After both loops complete, return `count`.

# Solutions
### CSharp

```csharp
public class Solution {
    public int CountGoodTriplets(int[] arr, int a, int b, int c) {
        int n = arr.Length;
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    if (Math.Abs(arr[i] - arr[j]) <= a && Math.Abs(arr[j] - arr[k]) <= b && Math.Abs(arr[i] - arr[k]) <= c) {
                        ++ans;
                    }
                }
            }
        }
        return ans;
    }
}
```

### Java

```java
class Solution { public int countGoodTriplets ( int [] arr , int a , int b , int c ) { int n = arr . length ; int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = i + 1 ; j < n ; ++ j ) { for ( int k = j + 1 ; k < n ; ++ k ) { if ( Math . abs ( arr [ i ] - arr [ j ]) <= a && Math . abs ( arr [ j ] - arr [ k ]) <= b && Math . abs ( arr [ i ] - arr [ k ]) <= c ) { ++ ans ; } } } } return ans ; } }
```

### CPP

```cpp
class Solution { public: int countGoodTriplets ( vector < int >& arr , int a , int b , int c ) { int n = arr . size (); int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = i + 1 ; j < n ; ++ j ) { for ( int k = j + 1 ; k < n ; ++ k ) { ans += abs ( arr [ i ] - arr [ j ]) <= a && abs ( arr [ j ] - arr [ k ]) <= b && abs ( arr [ i ] - arr [ k ]) <= c ; } } } return ans ; } };
```

### Python

```python
class Solution : def countGoodTriplets ( self , arr : List [ int ], a : int , b : int , c : int ) -> int : ans , n = 0 , len ( arr ) for i in range ( n ): for j in range ( i + 1 , n ): for k in range ( j + 1 , n ): ans += ( abs ( arr [ i ] - arr [ j ]) <= a and abs ( arr [ j ] - arr [ k ]) <= b and abs ( arr [ i ] - arr [ k ]) <= c ) return ans
```