# Leetcode – Count Good Triplets Solution

The “Count Good Triplets” problem on Leetcode offers a great opportunity to explore multiple facets of algorithmic design, from the naive brute-force solutions to optimized techniques. This in-depth article will dissect the problem statement, provide multiple methods to solve it, analyze their time and space complexities.

## Problem Statement

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 considered good if the following conditions are true:

1. 0 <= i < j < k < arr.length
2. |arr[i] – arr[j]| <= a
3. |arr[j] – arr[k]| <= b
4. |arr[i] – arr[k]| <= c

#### Example

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)].

## The Brute-Force Approach

The most straightforward approach to solving this problem is to generate all possible triplets and check each one for the given conditions.

Python Code:

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

# Test the function
print(countGoodTriplets([3, 0, 1, 1, 9, 7], 7, 2, 3))  # Output should be 4

### Time Complexity

The time complexity for this brute-force approach is O(n^3), where n is the length of the array.

### Space Complexity

The space complexity is O(1) as we only use a constant amount of extra space.

## Optimized Approach: Pairwise Preprocessing

Although this problem doesn’t lend itself to significantly optimized solutions due to the three conditions that must be satisfied, some minor optimizations can be made by pre-processing information about pairs of elements to reduce some computational overhead.

We can create an auxiliary array where the value at index (i, j) holds True if abs(arr[i] - arr[j]) <= a. This will eliminate the need to repeatedly calculate this value for each triplet. Similar arrays can be created for b and c conditions as well.

### Time and Space Complexity

Although the time complexity remains O(n^3), this approach might offer some real-time efficiency. The space complexity, however, increases to O(n^2) due to the additional arrays.

## Edge Cases and Additional Considerations

1. Empty Array: What if the input array is empty? The function should return 0 as no triplet can be formed.
2. Array of Length Less Than 3: Similar to the empty array, if the array has fewer than 3 elements, no triplet can be formed, and the answer should be 0.
3. Negative Numbers: The function should be able to handle arrays containing negative numbers as well.

## Conclusion

The “Count Good Triplets” problem, although not complex, provides an excellent exercise in understanding brute-force approaches and thinking about possible optimizations. While the naive brute-force approach is straightforward, we discussed a slightly optimized approach that uses pairwise preprocessing to gain some efficiency.

While this problem does not have a significantly optimized solution due to its inherent complexity, it serves as a great example to hone one’s skills in tackling problems with multiple conditions and constraints. Moreover, it opens up discussions about real-world applications and considerations for various edge cases, making it an interesting problem for both beginners and experienced coders alike.