Problem Description

You are given an array of integers arr and three integer values a, b, and c. Your task is to count how many "good triplets" exist in the array.

A triplet consists of three elements from the array: (arr[i], arr[j], arr[k]). For a triplet to be considered "good", it must satisfy all of the following conditions:

1. The indices must be in strictly increasing order: 0 <= i < j < k < arr.length
2. The absolute difference between the first and second elements must not exceed a: |arr[i] - arr[j]| <= a
3. The absolute difference between the second and third elements must not exceed b: |arr[j] - arr[k]| <= b
4. The absolute difference between the first and third elements must not exceed c: |arr[i] - arr[k]| <= c

Here, |x| represents the absolute value of x.

For example, if arr = [3, 0, 1, 1, 9, 7], a = 7, b = 2, and c = 3:

• The triplet (arr[0], arr[2], arr[3]) = (3, 1, 1) is good because:
  • |3 - 1| = 2 <= 7 (satisfies condition with a)
  • |1 - 1| = 0 <= 2 (satisfies condition with b)
  • |3 - 1| = 2 <= 3 (satisfies condition with c)

Your goal is to return the total count of all good triplets in the array.

Intuition

Since we need to find triplets that satisfy specific conditions on their pairwise differences, the most straightforward approach is to check every possible triplet in the array.

The key insight is that we're looking for combinations of three elements where their indices follow a specific order (i < j < k). This naturally leads us to think about using three nested loops - one for each position in the triplet.

For each potential triplet, we need to verify three conditions involving absolute differences. The brute force approach works well here because:

1. We must examine the relationships between all three pairs of elements: (arr[i], arr[j]), (arr[j], arr[k]), and (arr[i], arr[k])
2. There's no obvious way to predict whether a triplet will be "good" without actually checking all three conditions
3. The conditions are interdependent - even if two elements satisfy one condition, we can't guarantee the third element will make a valid triplet

The solution naturally emerges as a triple nested loop where:

• The outer loop picks the first element at index i
• The middle loop picks the second element at index j (where j > i)
• The inner loop picks the third element at index k (where k > j)

For each combination, we simply check if all three absolute difference conditions are met. If they are, we count it as a good triplet. This exhaustive search guarantees we won't miss any valid triplets while maintaining the required index ordering.

Solution Approach

The implementation uses a brute force enumeration approach with three nested loops to check all possible triplets.

Algorithm Steps:

1. Initialize a counter ans to 0 to keep track of good triplets, and get the length n of the input array.

2. Use three nested loops to generate all possible triplets with indices (i, j, k):

   • The outer loop iterates i from 0 to n-1
   • The middle loop iterates j from i+1 to n-1 (ensuring j > i)
   • The inner loop iterates k from j+1 to n-1 (ensuring k > j)

3. For each triplet (arr[i], arr[j], arr[k]), check all three conditions:

   • abs(arr[i] - arr[j]) <= a
   • abs(arr[j] - arr[k]) <= b
   • abs(arr[i] - arr[k]) <= c

4. If all three conditions are satisfied (using logical AND), increment the counter by 1. In Python, this is elegantly done by adding the boolean result (which evaluates to 1 for True, 0 for False).

5. After checking all possible triplets, return the final count.

Time Complexity: O(n³) where n is the length of the array, as we have three nested loops each iterating through the array.

Space Complexity: O(1) as we only use a constant amount of extra space for the counter and loop variables.

The solution leverages Python's ability to treat boolean expressions as integers (True = 1, False = 0), allowing us to directly add the result of the condition check to our answer counter. This makes the code more concise while maintaining readability.

Example Walkthrough

Let's walk through a small example to illustrate the solution approach.

Input: arr = [1, 5, 3, 2], a = 2, b = 3, c = 4

We'll systematically check all possible triplets using three nested loops:

Step 1: Initialize

• ans = 0 (counter for good triplets)
• n = 4 (array length)

Step 2: Iterate through all triplets

When i = 0 (arr[0] = 1):

• When j = 1 (arr[1] = 5):
  • When k = 2 (arr[2] = 3):
    • Triplet: (1, 5, 3)
    • Check: |1-5| = 4 > 2 (fails condition with a)
    • Not a good triplet
  • When k = 3 (arr[3] = 2):
    • Triplet: (1, 5, 2)
    • Check: |1-5| = 4 > 2 (fails condition with a)
    • Not a good triplet
• When j = 2 (arr[2] = 3):
  • When k = 3 (arr[3] = 2):
    • Triplet: (1, 3, 2)
    • Check: |1-3| = 2 ≤ 2 ✓, |3-2| = 1 ≤ 3 ✓, |1-2| = 1 ≤ 4 ✓
    • All conditions satisfied! ans = 1

When i = 1 (arr[1] = 5):

• When j = 2 (arr[2] = 3):
  • When k = 3 (arr[3] = 2):
    • Triplet: (5, 3, 2)
    • Check: |5-3| = 2 ≤ 2 ✓, |3-2| = 1 ≤ 3 ✓, |5-2| = 3 ≤ 4 ✓
    • All conditions satisfied! ans = 2

When i = 2 (arr[2] = 3):

• When j = 3 (arr[3] = 2):
  • No valid k (k must be > j = 3, but array ends at index 3)

Step 3: Return result

• Total good triplets found: 2

The algorithm correctly identifies the two good triplets: (1, 3, 2) at indices (0, 2, 3) and (5, 3, 2) at indices (1, 2, 3).

Solution Implementation

Time and Space Complexity

The time complexity is O(n³), where n is the length of the array arr. This is because the code uses three nested loops:

• The outer loop runs from i = 0 to n-1, executing n times
• The middle loop runs from j = i+1 to n-1, executing approximately n-i-1 times for each i
• The inner loop runs from k = j+1 to n-1, executing approximately n-j-1 times for each j

The total number of iterations is the number of ways to choose 3 indices from n elements, which is C(n,3) = n(n-1)(n-2)/6 = O(n³).

The space complexity is O(1) because the algorithm only uses a constant amount of extra space. The variables ans, n, i, j, and k are the only additional storage used, regardless of the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Inefficient Early Termination Opportunities

The brute force solution checks all three conditions for every triplet, even when early termination could save computation time. If the first condition |arr[i] - arr[j]| <= a fails, there's no need to continue checking that particular j with the current i for any k values.

Solution: Add early termination by checking conditions progressively:

class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        count = 0
        n = len(arr)
      
        for i in range(n):
            for j in range(i + 1, n):
                # Early termination: if first condition fails, skip to next j
                if abs(arr[i] - arr[j]) > a:
                    continue
                  
                for k in range(j + 1, n):
                    # Check remaining conditions only if first condition passed
                    if (abs(arr[j] - arr[k]) <= b and 
                        abs(arr[i] - arr[k]) <= c):
                        count += 1
      
        return count

2. Index Boundary Optimization

The current solution iterates i all the way to n-1, but since we need at least 3 elements for a triplet, we can stop earlier.

Solution: Optimize loop boundaries:

class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        count = 0
        n = len(arr)
      
        # Stop i at n-3 since we need at least 2 more elements after i
        for i in range(n - 2):
            # Stop j at n-2 since we need at least 1 more element after j
            for j in range(i + 1, n - 1):
                if abs(arr[i] - arr[j]) > a:
                    continue
                  
                for k in range(j + 1, n):
                    if (abs(arr[j] - arr[k]) <= b and 
                        abs(arr[i] - arr[k]) <= c):
                        count += 1
      
        return count

3. Missing Edge Case Handling

While the original solution handles most cases correctly, developers might forget to validate input constraints or handle edge cases like very small arrays.

Solution: Add input validation:

class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        # Handle edge case: array too small for any triplet
        if len(arr) < 3:
            return 0
          
        count = 0
        n = len(arr)
      
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                if abs(arr[i] - arr[j]) > a:
                    continue
                  
                for k in range(j + 1, n):
                    if (abs(arr[j] - arr[k]) <= b and 
                        abs(arr[i] - arr[k]) <= c):
                        count += 1
      
        return count

These optimizations can provide modest performance improvements, especially for larger arrays or when many triplets fail the first condition.