Count Good Triplets

We are given an array of integers, and we need to find the count of good triplets satisfying certain conditions. Let’s break down the solution into a simple approach.

Approach

We will run three nested loops to generate all possible triplets from the array. For each triplet (arr[i], arr[j], arr[k]), we will check whether it satisfies all the given conditions. If yes, we will increment the count of good triplets.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        count = 0

        # Iterate through all possible triplets
        for i in range(len(arr)):
            for j in range(i+1, len(arr)):
                for k in range(j+1, len(arr)):

                    # Check if the conditions are satisfied
                    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

Example

For arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3, the function would return 4, as there are four good triplets that satisfy the conditions.

Complexity

The time complexity of this solution is O(n^3), where n is the length of the given array arr, as we iterate through the array three times to generate all possible triplets. The space complexity is O(1), as we only use a constant amount of extra space.