LeetCode 1534 - Count Good Triplets

Difficulty: 🟢 Easy
Topics: Array, Enumeration

Solution

Problem Understanding

The problem asks us to count the number of good triplets in an integer array arr based on three difference constraints a, b, and c. A triplet (arr[i], arr[j], arr[k]) is considered good if it satisfies three conditions simultaneously: the indices i, j, and k are strictly increasing (0 <= i < j < k < arr.length), and the absolute differences between the elements meet the thresholds: |arr[i] - arr[j]| <= a, |arr[j] - arr[k]| <= b, and |arr[i] - arr[k]| <= c.

In simpler terms, we are looking for all combinations of three distinct elements in the array (in order) whose pairwise differences satisfy the given bounds. The input arr can have up to 100 elements, each integer between 0 and 1000, and the difference thresholds are also between 0 and 1000. This limited array size allows us to consider a brute-force solution with three nested loops because the total number of triplets is at most 100 choose 3 = 161700, which is computationally feasible.

Important edge cases include arrays where no triplet satisfies the condition (e.g., all differences exceed the thresholds), arrays where all elements are the same (all differences are zero), and arrays at the minimum length of 3. The problem guarantees that the array has at least 3 elements, so we do not need to handle smaller inputs.

Approaches

The brute-force approach is straightforward: we generate every possible triplet (i, j, k) where i < j < k and check if all three difference conditions are satisfied. This is guaranteed to find all good triplets because it exhaustively examines every candidate, but it uses three nested loops, resulting in O(n^3) time complexity. Given the constraints (n <= 100), this approach is acceptable.

There is no significantly faster approach in terms of worst-case complexity for this problem because we must examine each triplet to ensure all conditions are satisfied. Given the small input size, optimizing further (e.g., with sorting or prefix structures) offers no meaningful asymptotic improvement. The key insight is that the problem's constraints are small enough that the brute-force approach is effectively optimal.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n^3)	O(1)	Three nested loops over all triplets; directly counts valid triplets
Optimal	O(n^3)	O(1)	Same as brute force due to small input size; cannot asymptotically improve

Algorithm Walkthrough

Initialize a counter count to zero. This will hold the number of good triplets found.
Iterate over the first index i from 0 to len(arr) - 3. This represents the first element of the triplet.
For each i, iterate over the second index j from i + 1 to len(arr) - 2. This ensures j > i and avoids duplicate triplets.
For each j, iterate over the third index k from j + 1 to len(arr) - 1. This ensures k > j and maintains the increasing order of indices.
For each triplet (i, j, k), compute the absolute differences: |arr[i] - arr[j]|, |arr[j] - arr[k]|, and |arr[i] - arr[k]|.
If all three differences are within their respective thresholds a, b, and c, increment count by 1.
After checking all possible triplets, return count.

Why it works: By iterating through every combination of three distinct elements in increasing index order, we ensure no valid triplet is missed. The conditional checks guarantee that only triplets satisfying all three absolute difference constraints are counted.

Python Solution

from typing import List

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 - 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

This implementation first iterates over the indices i and j. It applies an early continue check for the first difference |arr[i] - arr[j]| > a to skip unnecessary computations for k. Then, for each valid (i, j) pair, it iterates over k and checks the remaining two differences. The use of abs ensures that we handle negative differences correctly. The counter count accumulates the number of good triplets and is returned at the end.

Go Solution

func countGoodTriplets(arr []int, a int, b int, c int) int {
    count := 0
    n := len(arr)
    for i := 0; i < n-2; i++ {
        for j := i + 1; j < n-1; j++ {
            if abs(arr[i]-arr[j]) > a {
                continue
            }
            for k := j + 1; k < n; k++ {
                if abs(arr[j]-arr[k]) <= b && abs(arr[i]-arr[k]) <= c {
                    count++
                }
            }
        }
    }
    return count
}

func abs(x int) int {
    if x < 0 {
        return -x
    }
    return x
}

In Go, we define a helper function abs because Go does not provide a built-in abs for integers. The iteration structure mirrors the Python solution. The continue optimization skips unnecessary iterations for invalid (i, j) pairs, reducing redundant computation.

Worked Examples

Example 1: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3

|---|---|---|--------|--------|--------|----------------|----------------|----------------|-------|

| 0 | 1 | 2 | 3 | 0 | 1 | 3 | 1 | 2 | Yes |

| 0 | 1 | 3 | 3 | 0 | 1 | 3 | 1 | 2 | Yes |

| 0 | 2 | 3 | 3 | 1 | 1 | 2 | 0 | 2 | Yes |

| 1 | 2 | 3 | 0 | 1 | 1 | 1 | 0 | 1 | Yes |

Total count = 4.

Example 2: arr = [1,1,2,2,3], a = 0, b = 0, c = 1

No triplet satisfies all conditions, so count = 0.

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^3)	Three nested loops over indices `i`, `j`, `k`. Early `continue` may save some iterations but does not change worst-case.
Space	O(1)	Only a counter and loop variables are used. No extra data structures required.

The time complexity is acceptable given the constraint n <= 100, yielding at most 161700 iterations.

Test Cases

# Provided examples
assert Solution().countGoodTriplets([3,0,1,1,9,7], 7, 2, 3) == 4  # example 1
assert Solution().countGoodTriplets([1,1,2,2,3], 0, 0, 1) == 0  # example 2

# Edge cases
assert Solution().countGoodTriplets([0,0,0], 0, 0, 0) == 1  # all differences zero, single triplet
assert Solution().countGoodTriplets([1,2,3,4], 10, 10, 10) == 4  # all triplets satisfy large thresholds
assert Solution().countGoodTriplets([1,2,3], 0, 0, 0) == 0  # differences too large
assert Solution().countGoodTriplets([5,5,5,5], 0, 0, 0) == 4  # all triplets are good, identical elements
assert Solution().countGoodTriplets([1,3,6,10], 2, 2, 5) == 0  # no triplet satisfies constraints

Test	Why
`[3,0,1,1,9,