Domain 1EasyCORE

Count Good Triplets

The problem requires us to count the number of "good" triplets in an array `arr`. A triplet `(arr[i], arr[j], arr[k])` is considered good if it satisfies three conditions: 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`

Domain: Easy•Updated: 2026-08-31
#Algorithms#LeetCode#qwen2.5-coder:14b#Array

1534. Count Good Triplets

Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 80.3%


Problem Breakdown

The problem requires us to count the number of “good” triplets in an array arr. A triplet (arr[i], arr[j], arr[k]) is considered good if it satisfies three conditions:

  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

Inputs:

  • An array of integers arr.
  • Three integers a, b, and c.

Outputs:

  • The number of good triplets.

Implicit Constraints or Edge Cases:

  • The array length is between 3 and 100.
  • Array elements are between 0 and 1000.
  • a, b, and c are non-negative integers up to 1000.
  • The array can contain duplicate values.

Intuition

The brute-force approach would involve checking all possible triplets (i, j, k) where 0 <= i < j < k < arr.length. For each triplet, we would verify if it satisfies the three conditions. This approach has a time complexity of (O(n^3)), which is inefficient given the constraints.

A better approach involves iterating through all possible pairs (i, j) and then checking for valid k values that satisfy the conditions with respect to both arr[i] and arr[j]. This reduces the number of checks needed and optimizes the solution.

Approach

  1. Initialize a counter good_triplets_count to zero.
  2. Iterate through all possible pairs (i, j) where 0 <= i < j < arr.length.
  3. For each pair (i, j), check if |arr[i] - arr[j]| <= a. If not, skip to the next pair.
  4. For valid pairs (i, j), iterate through all possible k values where j < k < arr.length.
  5. Check if both |arr[j] - arr[k]| <= b and |arr[i] - arr[k]| <= c are satisfied.
  6. If the conditions are met, increment the good_triplets_count.
  7. Return the good_triplets_count.

Complexity Analysis

  • Time Complexity: (O(n^2))

    • We iterate through all pairs (i, j) which takes (O(n^2)) time.
    • For each pair, we check valid k values, which in the worst case is (O(n)), but on average will be much less due to the constraints.
  • Space Complexity: (O(1))

    • We use a constant amount of extra space for variables and counters.

Solution

def countGoodTriplets(arr, a, b, c):
    good_triplets_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:
                for k in range(j + 1, n):
                    if abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c:
                        good_triplets_count += 1
    
    return good_triplets_count

Edge Cases Handled

  • All elements are the same: The code will correctly count triplets where all elements are equal, as long as they satisfy the conditions.
  • No valid triplets exist: If no triplet satisfies the conditions, the function returns 0.
  • Array length is exactly 3: The function handles this by iterating through all possible triplets without any issues.