{x}
blog image

Count Good Triplets

Given an array of integers arr, and three integers a, b and c. You need to find the number of good triplets.

A triplet (arr[i], arr[j], arr[k]) is good if the following conditions are true:

  • 0 <= i < j < k < arr.length
  • |arr[i] - arr[j]| <= a
  • |arr[j] - arr[k]| <= b
  • |arr[i] - arr[k]| <= c

Where |x| denotes the absolute value of x.

Return the number of good triplets.

 

Example 1:

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4
Explanation: There are 4 good triplets: [(3,0,1), (3,0,1), (3,1,1), (0,1,1)].

Example 2:

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output: 0
Explanation: No triplet satisfies all conditions.

 

Constraints:

  • 3 <= arr.length <= 100
  • 0 <= arr[i] <= 1000
  • 0 <= a, b, c <= 1000

Solution Explanation: Counting Good Triplets

The problem asks to find the number of "good triplets" in an array. A triplet (arr[i], arr[j], arr[k]) is considered good if it meets three conditions:

  1. Index Order: 0 ≤ i < j < k < arr.length
  2. Absolute Difference Constraints: |arr[i] - arr[j]| ≤ a, |arr[j] - arr[k]| ≤ b, and |arr[i] - arr[k]| ≤ c.

Approach: Brute-Force Enumeration

The most straightforward approach is to iterate through all possible triplets (i, j, k) that satisfy the index order condition (condition 1) and check if they satisfy the absolute difference constraints (condition 2). We increment a counter for each triplet that meets all conditions.

Time and Space Complexity Analysis

  • Time Complexity: The nested loops iterate through all possible triplets. The number of such triplets is O(n³), where n is the length of the input array arr. Therefore, the time complexity is O(n³).

  • Space Complexity: The solution uses a constant amount of extra space to store the counter variable ans. Therefore, the space complexity is O(1).

Code Implementation in Multiple Languages

The following code demonstrates the brute-force approach in several programming languages:

Python:

class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        ans = 0  # Initialize the counter for good triplets
        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):
                        ans += 1  # Increment the counter if all conditions are met
        return ans

Java:

class Solution {
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int ans = 0; // Initialize the counter for good triplets
        int n = arr.length;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (Math.abs(arr[i] - arr[j]) <= a &&
                        Math.abs(arr[j] - arr[k]) <= b &&
                        Math.abs(arr[i] - arr[k]) <= c) {
                        ans++; // Increment the counter if all conditions are met
                    }
                }
            }
        }
        return ans;
    }
}

C++:

class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int ans = 0; // Initialize the counter for good triplets
        int n = arr.size();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (abs(arr[i] - arr[j]) <= a &&
                        abs(arr[j] - arr[k]) <= b &&
                        abs(arr[i] - arr[k]) <= c) {
                        ans++; // Increment the counter if all conditions are met
                    }
                }
            }
        }
        return ans;
    }
};

JavaScript:

const countGoodTriplets = (arr, a, b, c) => {
    let ans = 0; // Initialize the counter for good triplets
    const n = arr.length;
    for (let i = 0; i < n; i++) {
        for (let j = i + 1; j < n; j++) {
            for (let k = j + 1; k < n; k++) {
                if (Math.abs(arr[i] - arr[j]) <= a &&
                    Math.abs(arr[j] - arr[k]) <= b &&
                    Math.abs(arr[i] - arr[k]) <= c) {
                    ans++; // Increment the counter if all conditions are met
                }
            }
        }
    }
    return ans;
};

These code examples all follow the same basic brute-force strategy. They differ only in syntax and specific library functions used for absolute value calculation. For larger input arrays, more optimized algorithms might be necessary to improve performance, but for the given constraints (arr.length ≤ 100), this brute-force approach is efficient enough.