1534. Count Good Triplets

EasyView on LeetCode

Array enumeration

Time: O(n³)

Space: O(1)

Problem Overview

Count triplets (i, j, k) with i < j < k where all three pairwise differences are within limits a, b, and c.

Intuition

Count triplets (i, j, k) with i < j < k where all three pairwise differences are within limits a, b, and c. Constraints are small (n <= 100), so checking every triplet is acceptable. All three conditions must hold simultaneously.

Algorithm

1Initialize count = 0.
2Triple loop: for i in 0..n-3, j in i+1..n-2, k in j+1..n-1.
3If abs(arr[i]-arr[j]) <= a AND abs(arr[j]-arr[k]) <= b AND abs(arr[i]-arr[k]) <= c: count++.
4Return count.

Example Walkthrough

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

1.Valid triplets include (0,2,3) -> |3-1|,|1-1|,|3-1| all within limits.

Output: 4

Common Pitfalls

•Check all three pairwise gaps — not just adjacent pairs in the triplet.
•Indices must be strictly increasing i < j < k.
•Brute force O(n^3) is intended for n <= 100.

1534.cs

// Approach: Brute-force O(n³) check all triplets i<j<k satisfying all three difference constraints.
// Time: O(n³) Space: O(1)

public class Solution
{
    public int CountGoodTriplets(int[] arr, int a, int b, int c)
    {
        int ans = 0;

        for (int i = 0; i < arr.Length; ++i)
        {
            for (int j = i + 1; j < arr.Length; ++j)
            {
                for (int k = j + 1; k < arr.Length; ++k)
                {
                    if (Math.Abs(arr[i] - arr[j]) <= a &&
                        Math.Abs(arr[j] - arr[k]) <= b &&
                        Math.Abs(arr[i] - arr[k]) <= c)
                        ++ans;
                }
            }
        }

        return ans;
    }
}

Was this solution helpful?