Count Good Triplets

Problem Description

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

Return the number of good triplets.

Key Insights

• Triplets are defined by three indices i, j, and k, with i < j < k.
• The conditions involve absolute differences between the array elements, which can be efficiently checked.
• The constraints allow for a brute-force approach due to the maximum length of the array being 100, leading to a maximum of 161700 triplet combinations.

Space and Time Complexity

Time Complexity: O(n^3)
Space Complexity: O(1)

Solution

The solution involves a straightforward brute-force approach where we iterate through all possible triplets (i, j, k) that satisfy the index constraints (i < j < k). For each triplet, we will check if the absolute differences between the elements meet the specified conditions. Given the constraints of the problem, this approach is feasible.

1. Initialize a counter for good triplets.
2. Use three nested loops to iterate through all combinations of indices i, j, and k.
3. For each combination, check the three conditions involving absolute differences.
4. If all conditions are satisfied, increment the counter.
5. Return the total count of good triplets.

Code Solutions