Count Good Triplets

main.md

Question

Approach

To solve this problem, I looped through every possible triplet of indices (i < j < k), but I made sure to add some early checks to avoid unnecessary computations. First, I checked whether (|arr[i] - arr[j]|) was less than or equal to a. If not, I skipped checking for k entirely, since the triplet would never be valid. Only when that condition passed did I move on to the innermost loop for k, where I checked the remaining two conditions: (|arr[j] - arr[k]| \leq b) and (|arr[i] - arr[k]| \leq c) before counting the triplet.

Implementation

class Solution:
    def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
        count = 0
        n = len(arr)
        for i in range(n - 2):
            for j in range(i + 1, n - 1):
                if abs(arr[i] - arr[j]) > a:
                    continue  # skip early
                for k in range(j + 1, n):
                    if abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c:
                        count += 1
        return count

Complexities

• Time: O(n^2)
• Space: O(1)