Count Good Triplets: Triple Loop with Conditions

LeetCode Count Good Triplets asks you to find all triplets (arr[i], arr[j], arr[k]) in an integer array where 0 <= i < j < k < arr.length and three absolute difference conditions are all satisfied: |arr[i] - arr[j]| <= a, |arr[j] - arr[k]| <= b, and |arr[i] - arr[k]| <= c.

Given the array [3, 0, 1, 1, 9, 7] with a = 7, b = 2, c = 3, the answer is 4. Four triplets pass every condition.

Why this problem matters

This is one of those rare problems where brute force is the intended solution. The array length is at most 100, which means the maximum number of triplets is roughly 100 * 99 * 98 / 6, about 161,000. That is well within the limits of a triple loop running in under a second.

The real value of this problem is not in finding a clever optimization. It is in practicing the enumeration pattern: systematically generating all combinations and filtering by conditions. You will see this pattern again in problems like 3Sum, 4Sum, and many backtracking problems. The difference is that those problems have larger inputs and require you to optimize. Here, you get to focus purely on the mechanics of multi-index iteration and condition checking.

The key insight

With n <= 100, an O(n^3) solution runs at most about 10^6 operations. That is fast enough for any judge. So the approach is simple: try every valid combination of (i, j, k) and count the ones where all three conditions hold.

One useful optimization: check |arr[i] - arr[j]| <= a in the middle loop, before entering the innermost loop. If this condition fails, you can skip all values of k for that (i, j) pair. This pruning does not change the worst-case complexity, but it can cut the actual runtime significantly when a is small.

The solution

def countGoodTriplets(arr, a, b, c):
    count = 0
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            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

The outer two loops pick i and j. Before entering the k loop, we check the first condition. If |arr[i] - arr[j]| exceeds a, we skip to the next j immediately. For every valid (i, j) pair, the inner loop tries each k and checks the remaining two conditions.

Visual walkthrough

The algorithm exhaustively checks all triplets. Steps 1 through 3 show cases where every condition passes, incrementing the count each time. Step 4 shows a triplet that fails the third condition (|arr[i] - arr[k]| is 4, which exceeds c = 3), so it gets skipped. After examining all possible triplets, the final count is 4.

Complexity analysis

Time: Three nested loops over the array produce O(n^3) combinations in the worst case. With n <= 100, this is at most about 10^6 operations, which runs in milliseconds.

Space: We only use a counter variable. No extra data structures are needed, so the space is O(1).

The building blocks

1. Multi-index enumeration

The core pattern here is generating all ordered triples (i, j, k) where i < j < k. You do this with three nested loops, each starting one past the previous index. This same structure appears in 3Sum, combination generation, and any problem that asks you to examine all subsets of a fixed size.

for i in range(n):
    for j in range(i + 1, n):
        for k in range(j + 1, n):
            pass

2. Absolute difference filtering

Each triplet is tested against threshold conditions using absolute differences. The abs(x - y) function measures how far apart two values are. Filtering by abs(x - y) <= threshold is a pattern that shows up in problems involving proximity, tolerance windows, and range queries.

if abs(arr[i] - arr[j]) <= a:
    pass

Edge cases

All elements identical. If every element is the same, then every absolute difference is 0. As long as a, b, and c are all at least 0 (which is guaranteed by the constraints), every triplet is good. The answer is n * (n-1) * (n-2) / 6.

Array of length 3. There is exactly one possible triplet. You check the three conditions and return either 0 or 1.

Very strict thresholds. If a, b, or c is 0, only triplets where the corresponding pair of elements are equal will pass that condition. The code handles this naturally since abs(x - y) <= 0 means x == y.

Very loose thresholds. If all thresholds are large enough (say, 200 when values range from 0 to 100), every triplet is good. The answer again simplifies to the combinatorial formula.

From understanding to recall

Count Good Triplets is intentionally simple. The algorithm is a direct translation of the problem statement into three nested loops. But that directness is exactly what makes it a good drill problem.

The patterns here (multi-index enumeration and early pruning with continue) are the same ones you will use in harder problems. In 3Sum, you enumerate pairs and binary search or two-pointer for the third element. In combination sum, you enumerate with backtracking. The muscle memory of writing for j in range(i + 1, n) and checking conditions at the right level of nesting transfers directly.

Drilling this problem with spaced repetition helps you internalize the loop structure so that when you see a harder variant, you spend your mental energy on the optimization rather than the scaffolding.

Related posts

• Contains Duplicate - Foundational array checking problem
• Two Sum - Checking pair conditions in an array
• 3Sum - Another triplet-based problem with different optimization

Count Good Triplets is a warm-up, but the enumeration pattern it drills is the foundation for a whole family of harder problems. Once you can write the triple loop and apply conditions without hesitation, you are ready to start optimizing it away.