Leetcode – Count Good Triplets Solution

Spread the love

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.

Leave a Reply