Problem Description

The "Count Good Triplets" problem asks you to count the number of good triplets in an array of integers. A triplet (i, j, k) is called good if it satisfies the following conditions:

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

You must find the total number of such good triplets without reusing the same element at different indices. Each triplet must have strictly increasing indices.

Thought Process

At first glance, the problem suggests checking every possible combination of three indices in the array. This would mean using three nested loops to check all triplets. For each triplet, we would check if all three conditions are satisfied.

However, this brute-force approach can be slow for larger arrays because the number of triplets grows quickly as the array size increases. Therefore, after considering the brute-force approach, we look for optimizations. But, given the tight constraints on the indices and the direct conditions on the values, there are limited opportunities for significant optimization without overcomplicating the solution.

It's important to recognize that for small array sizes (as is the case in the original Leetcode problem), the brute-force approach is acceptable and often expected. For larger arrays, we might look into advanced techniques, but for this problem, clarity and correctness take precedence.

Solution Approach

We'll use a straightforward method to solve this problem:

1. Iterate over all possible triplets: Use three nested loops to generate all possible combinations of indices (i, j, k) where i < j < k.
2. Check the conditions: For each triplet, check if the absolute difference conditions are satisfied:
   • |arr[i] - arr[j]| <= a
   • |arr[j] - arr[k]| <= b
   • |arr[i] - arr[k]| <= c
3. Count valid triplets: If all conditions are met, increment a counter.
4. Return the result: After checking all triplets, return the counter as the answer.

This approach is simple, easy to understand, and leverages the manageable input size. While it is possible to try to optimize further (for example, by pre-sorting or using data structures to speed up lookups), the improvement would be marginal for the typical input sizes of this problem.

Example Walkthrough

Let's walk through a sample input:

Input: arr = [3, 0, 1, 1, 9, 7], a = 7, b = 2, c = 3

We'll look for all triplets (i, j, k) such that i < j < k:

• Start with i = 0 (arr[0] = 3)
• For j = 1 (arr[1] = 0), check k from 2 to 5:
  • k = 2 (arr[2]=1): |3-0|=3 <=7, |0-1|=1 <=2, |3-1|=2 <=3 → Valid
  • k = 3 (arr[3]=1): same as above → Valid
  • k = 4 (arr[4]=9): |0-9|=9 >2 → Not valid
  • k = 5 (arr[5]=7): |0-7|=7 >2 → Not valid
• Continue with other combinations for j and k, checking each condition.

After checking all combinations, we find there are 4 good triplets in this example.

Time and Space Complexity

Brute-force Approach:

• Time Complexity: O(n^3) because we use three nested loops, each iterating up to n (the length of arr).
• Space Complexity: O(1) since we only use a counter variable and no extra data structures proportional to input size.

• For this problem, since the constraints are small, further optimization is not necessary. If constraints were larger, we might try to reduce the number of checks by sorting or using advanced data structures, but that is not required here.

Code Implementation

class Solution:
    def countGoodTriplets(self, arr, a, b, c):
        n = len(arr)
        count = 0
        for i in range(n):
            for j in range(i+1, n):
                if abs(arr[i] - arr[j]) > a:
                    continue
                for k in range(j+1, n):
                    if abs(arr[j] - arr[k]) > b:
                        continue
                    if abs(arr[i] - arr[k]) <= c:
                        count += 1
        return count
      

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

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; i++) {
            for (int j = i + 1; j < n; j++) {
                if (Math.abs(arr[i] - arr[j]) > a) continue;
                for (int k = j + 1; k < n; k++) {
                    if (Math.abs(arr[j] - arr[k]) > b) continue;
                    if (Math.abs(arr[i] - arr[k]) <= c) {
                        count++;
                    }
                }
            }
        }
        return count;
    }
}
      

var countGoodTriplets = function(arr, a, b, c) {
    let n = arr.length;
    let count = 0;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            if (Math.abs(arr[i] - arr[j]) > a) continue;
            for (let k = j + 1; k < n; k++) {
                if (Math.abs(arr[j] - arr[k]) > b) continue;
                if (Math.abs(arr[i] - arr[k]) <= c) {
                    count++;
                }
            }
        }
    }
    return count;
};
      

Summary

The "Count Good Triplets" problem is a classic example of using nested loops to check all combinations under certain constraints. The three nested loops are justified by the small input size, ensuring the solution is efficient and easy to understand. The key insight is to check the absolute difference conditions in order, skipping unnecessary checks to slightly optimize the process. This approach balances clarity and correctness, making it a strong solution for the problem as stated.