Leetcode 1534. Count Good Triplets

Let's understand what we're being asked to do. We have an array like [1, 5, 3, 4, 2] and three threshold values a=2, b=3, c=4. We need to count how many triplets (i, j, k) where i < j < k satisfy ALL three conditions simultaneously.

Let's trace through one example triplet: indices (0, 2, 4) correspond to values (1, 3, 2). Check the conditions:

• |arr[0] - arr[2]| = |1 - 3| = 2 ≤ a=2 ✓
• |arr[2] - arr[4]| = |3 - 2| = 1 ≤ b=3 ✓
• |arr[0] - arr[4]| = |1 - 2| = 1 ≤ c=4 ✓

All three conditions are satisfied, so this triplet counts!

Important constraint: The array length is at most 100, which means there are at most 100 * 99 * 98 / 6 ≈ 161,700 possible triplets. This small size makes checking every triplet feasible.

Edge cases to consider: What if the array has fewer than 3 elements? (return 0). What if all values are the same? What if a, b, or c are 0 (very strict)?

With only 100 elements maximum, we can afford to check every possible triplet (i, j, k) where i < j < k. For each triplet, we compute three absolute differences and verify all three conditions.

The key insight is recognizing that the small input size makes the brute force approach practical - we don't need a clever optimization here.

Sometimes the most straightforward solution IS the right solution! With n ≤ 100, even an O(n³) algorithm runs in under a millisecond on modern hardware.

This is an important lesson: premature optimization can waste time. Always consider the constraints before reaching for complex algorithms.

Think about how you'd solve this by hand with a small array like [1, 3, 5]:

You'd naturally check the only triplet (0, 1, 2): compute |1-3|, |3-5|, and |1-5|, then verify against a, b, c.

With 100 elements, you'd do the same process systematically - three nested loops to generate all triplets, then three comparisons per triplet. The constraint-driven approach tells us this is perfectly acceptable.

Use three nested loops to generate all possible triplets (i, j, k) where i < j < k. For each triplet, compute the three absolute differences: |arr[i] - arr[j]|, |arr[j] - arr[k]|, and |arr[i] - arr[k]|. Check if all three differences satisfy their respective thresholds a, b, and c. If all conditions are met, increment the count. This direct enumeration approach is optimal given the small constraint of n ≤ 100.

def count_valid_triplets(arr, a, b, c):
    """
    Count triplets (i, j, k) where i < j < k and
    |arr[i]-arr[j]| <= a, |arr[j]-arr[k]| <= b, |arr[i]-arr[k]| <= c
    """
    n = len(arr)
    count = 0
    
    # Iterate through all possible triplets
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                # Calculate pairwise absolute differences
                diff_ij = abs(arr[i] - arr[j])
                diff_jk = abs(arr[j] - arr[k])
                diff_ik = abs(arr[i] - arr[k])
                
                # Check if all three conditions are satisfied
                if diff_ij <= a and diff_jk <= b and diff_ik <= c:
                    count += 1
    
    return count

• Brute force viability with constraint analysis: When array size is small (n ≤ 100), a O(n³) triple nested loop is perfectly acceptable - always check constraints before optimizing, as 100³ = 1,000,000 operations run in milliseconds and simpler code reduces bug risk.
• Sequential condition checking optimization: Evaluate conditions in order of computational cost - check |arr[i]-arr[j]| ≤ a first, then |arr[j]-arr[k]| ≤ b, and finally |arr[i]-arr[k]| ≤ c to short-circuit and skip unnecessary comparisons when early conditions fail.
• Index ordering enforcement: Use i < j < k loop structure (outer loop i: 0→n-3, middle loop j: i+1→n-2, inner loop k: j+1→n-1) to naturally guarantee the ordering constraint without additional checks - the loop bounds themselves enforce the triplet relationship.
• Absolute difference pattern: Problems involving pairwise comparisons with threshold constraints often require checking all combinations when no mathematical relationship exists between the constraints - recognize when conditions are independent and cannot be simplified algebraically.
• Space-time tradeoff awareness: This problem demonstrates choosing O(1) space with O(n³) time over complex optimizations - for small inputs, the simplicity of direct enumeration outweighs sophisticated data structures like coordinate compression or range trees that add implementation complexity.
• Combinatorial counting template: When counting valid tuples with multiple constraints, the pattern is: iterate all combinations, apply filters sequentially, increment counter - this enumerate-and-filter approach applies to many counting problems where constraints don't allow mathematical closed-form solutions.