Count Good Triplets

Good Triplets Solution

Problem Description

Given an array of integers arr and three integers a, b, and c, the goal is to find the number of "good" triplets. A triplet (arr[i], arr[j], arr[k]) is considered good if the following conditions are met:

1. 0 <= i < j < k < arr.length
2. |arr[i] - arr[j]| <= a
3. |arr[j] - arr[k]| <= b
4. |arr[i] - arr[k]| <= c

The task is to return the number of good triplets.

Naive (Brute Force) Solution

A straightforward approach is to iterate through all possible triplets and check if each triplet satisfies the given conditions. This involves three nested loops.

Code

def count_good_triplets_brute_force(arr, a, b, c):
    count = 0
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if abs(arr[i] - arr[j]) <= a and \
                   abs(arr[j] - arr[k]) <= b and \
                   abs(arr[i] - arr[k]) <= c:
                    count += 1
    return count

Time Complexity

The time complexity of the brute force approach is O(n^3) because it involves three nested loops, each iterating up to n times, where n is the length of the input array.

Space Complexity

The space complexity is O(1) because it uses a constant amount of extra space.

Optimal Solution

In this specific problem, since the constraints are small (array size up to 100), the brute force solution is already efficient enough and can be considered optimal due to its simplicity and directness. More complex solutions might involve pre-computation or sorting, but given the problem constraints, they are unlikely to offer significant performance improvements that would justify the added complexity.

Code (Same as Brute Force)

def count_good_triplets_optimal(arr, a, b, c):
    count = 0
    n = len(arr)
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                if abs(arr[i] - arr[j]) <= a and \
                   abs(arr[j] - arr[k]) <= b and \
                   abs(arr[i] - arr[k]) <= c:
                    count += 1
    return count

Time Complexity

The time complexity remains O(n^3).

Space Complexity

The space complexity remains O(1).

Edge Cases

• Empty Array: If the input array is empty or has fewer than 3 elements, the function should return 0, as no triplets can be formed.
• Zero Values for a, b, c: If a, b, or c are zero, the absolute differences must also be zero for the conditions to be met. This will likely reduce the number of good triplets.
• Large Values for a, b, c: If a, b, and c are very large, most triplets will likely satisfy the conditions, and the count will be close to the total number of possible triplets.

Summary

For the given problem constraints, the brute force solution is efficient and simple enough to be considered an optimal solution. It has a time complexity of O(n^3) and a space complexity of O(1).