Problem Informations

• Problem Index: 1534
• Problem Link: Count Good Triplets
• Topics: Array, Enumeration

Problem Description

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 \leq i < j < k < arr.length$
• $|arr[i] - arr[j]| \leq a$
• $|arr[j] - arr[k]| \leq b$
• $|arr[i] - arr[k]| \leq 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 \leq arr.length \leq 100$
• $0 \leq arr[i] \leq 1000$
• $0 \leq a, b, c \leq 1000$

Intuition

This problem requires us to identify triplets in an array that satisfy a set of conditions involving absolute differences. The conditions imposed create constraints on the selection of indices $(i, j, k)$ such that $0 \leq i < j < k < arr.length$. The primary intuition revolves around iterating through all possible triplet combinations within the array and validating them against the given conditions. To efficiently tackle this problem, we should focus on a systematic way to iterate over the array indices minimizing redundancy and ensuring all conditions are checked.

Approach

The algorithm employs a straightforward approach using three nested loops to generate all possible triplets $(arr[i], arr[j], arr[k])$. The following steps outline the approach in detail:

1. Initialize a Counter: Begin by initializing a counter goodTripletCount to zero. This will track the number of triplets that meet the specified conditions.

2. Iterate to Select the First Element: Use the first loop with iterator i to select the first element of the triplet. The loop runs from 0 to arr.size() - 2 to ensure there are at least two remaining elements for the next indices.

3. Iterate to Select the Second Element: Within the first loop, employ a second loop with iterator j running from i + 1 to arr.size() - 1. This guarantees that $j$ is always greater than $i$, maintaining the order required.

4. Check First Condition: Before selecting the third element, check if the absolute difference between arr[i] and arr[j] is less than or equal to $a$. If not, skip to the next iteration for $j$.

5. Iterate to Select the Third Element: If the first condition is satisfied, use a third loop with iterator k running from j + 1 to arr.size(). This ensures $k$ is always greater than $j$.

6. Check Remaining Conditions: For each triplet $(i, j, k)$, check the conditions $|arr[j] - arr[k]| \leq b$ and $|arr[i] - arr[k]| \leq c$. If both conditions hold, increment the goodTripletCount.

7. Return the Count: After all iterations, return goodTripletCount as the result, which represents the number of valid triplets.

This approach leverages a direct but exhaustive search within the constrained size of the input array, ensuring all possible combinations are evaluated without unnecessary calculations. The constraints of the problem and size of the array make this method computationally feasible.

Code

C++

class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        int goodTripletCount = 0;
        
        // Iterate through the array to select the first element of the triplet
        for (int i = 0; i < arr.size() - 2; i++) {
            // Iterate to select the second element of the triplet
            for (int j = i + 1; j < arr.size() - 1; j++) {
                // Check if the absolute difference between arr[i] and arr[j] is within the limit a
                if (abs(arr[j] - arr[i]) > a) continue;
                
                // Iterate to select the third element of the triplet
                for (int k = j + 1; k < arr.size(); k++) {
                    // Check both conditions for arr[j] with arr[k] and arr[i] with arr[k]
                    if (abs(arr[k] - arr[j]) <= b && abs(arr[k] - arr[i]) <= c) {
                        goodTripletCount++;
                    }
                }
            }
        }
        
        return goodTripletCount;
    }
};

Python

class Solution:
    def countGoodTriplets(self, arr, a, b, c):
        goodTripletCount = 0

        # Iterate through the array to select the first element of the triplet
        for i in range(len(arr) - 2):
            # Iterate to select the second element of the triplet
            for j in range(i + 1, len(arr) - 1):
                # Check if the absolute difference between arr[i] and arr[j] is within the limit a
                if abs(arr[j] - arr[i]) > a:
                    continue
                
                # Iterate to select the third element of the triplet
                for k in range(j + 1, len(arr)):
                    # Check both conditions for arr[j] with arr[k] and arr[i] with arr[k]
                    if abs(arr[k] - arr[j]) <= b and abs(arr[k] - arr[i]) <= c:
                        goodTripletCount += 1

        return goodTripletCount

Complexity

• Time complexity: $O(n^3)$ The given code iterates over the array to select triplet elements using three nested loops:

  1. The outermost loop iterates over the array to choose the first element of the triplet. It runs approximately $n-2$ times, where $n$ is the length of the array.
  2. The middle loop iterates to choose the second element of the triplet, running approximately $n-1-i$ times for each iteration of the outer loop.
  3. The innermost loop selects the third element of the triplet, iterating approximately $n-j$ times for each pair of i and j.

  Each of these loops contributes a factor to the overall time complexity, resulting in an overall complexity of $O(n^3)$. Given that the array’s length constraint is up to 100, this cubic complexity is feasible within the problem’s constraints.

• Space complexity: $O(1)$ The algorithm uses a fixed amount of extra space regardless of the input size. The space used by the algorithm is primarily defined by the integer goodTripletCount and the control variables for the loops (i, j, and k). As a result, the space complexity is constant, $O(1)$.