1534. Count Good Triplets

EasyView on LeetCode

Array enumeration

Time: O(n³)

Space: O(1)

Intuition

Count triplets (i<j<k) where abs(arr[i]-arr[j]) <= a, abs(arr[j]-arr[k]) <= b, abs(arr[i]-arr[k]) <= c.

Algorithm

1Three nested loops (O(n^3)) checking all triplets since n <= 100.

Common Pitfalls

•Brute force works for small n. Check all three conditions for each triplet.

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?