What is the time complexity of the Brute Force Enumeration approach?

The time complexity is O(n³), where n is the length of the array.

What is the space complexity of the Brute Force Enumeration approach?

The space complexity is O(1) as we only use a constant amount of extra space.

Count Good Triplets

Difficulty: Easy | Acceptance: 85.50% | Paid: No Topics: Array, Enumeration

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.

Examples
Constraints
Brute Force Enumeration

Examples

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

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

Brute Force Enumeration

Intuition Since the constraints on the array length are very small (n <= 100), we can afford to check every possible combination of three elements (i, j, k) using three nested loops.

Steps

Initialize a counter variable to 0.
Use three nested loops to iterate through all valid index triplets (i, j, k) where 0 <= i < j < k < n.
For each triplet, check if the three conditions involving absolute differences are satisfied.
If all conditions are met, increment the counter.
Return the counter after all loops finish.

python

class Solution:
    def countGoodTriplets(self, arr: list[int], a: int, b: int, c: int) -> int:
        n = len(arr)
        count = 0
        for i in range(n):
            for j in range(i + 1, n):
                if abs(arr[i] - arr[j]) &gt; a:
                    continue
                for k in range(j + 1, n):
                    if abs(arr[j] - arr[k]) &lt;= b and abs(arr[i] - arr[k]) &lt;= c:
                        count += 1
        return count

Complexity

Time: O(n³) — We iterate through all possible triplets using three nested loops.
Space: O(1) — We only use a few variables for counting and indices.
Notes: Given the constraint n <= 100, n³ is at most 1,000,000 operations, which is well within the time limit.