#1534

Easy

LeetCode Problem Workspace

Count Good Triplets

Count Good Triplets requires identifying all triplets in an array that satisfy multiple absolute difference constraints efficiently.

array enumeration

Problem Statement

Given an integer array arr and three integers a, b, and c, determine how many triplets (arr[i], arr[j], arr[k]) satisfy i < j < k and specific absolute difference rules. A triplet is considered good if all conditions are met simultaneously.

Examples

Example 1

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3

Output: 4

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

No triplet satisfies all conditions.

Constraints

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

Solution Approach

Brute-force Enumeration

Optimized Checks with Early Breaks

While enumerating, break inner loops early if a condition fails. For example, if |arr[i]-arr[j]| > a, skip further k iterations for that pair. This reduces unnecessary computation while still relying on the array plus enumeration pattern.

Avoid Duplicate Counting

Ensure indices i < j < k are strictly enforced. Using improper loop ranges or comparing the same indices more than once can inflate counts. Following the enumeration pattern correctly guarantees accurate results.

Complexity Analysis

Metric	Value
Time	O(n^2+nS)
Space	O(S)

Time complexity is O(n^3) in naive enumeration, but early breaks can reduce checks to roughly O(n^2) for most inputs. Space complexity is O(1) aside from storing input, as no additional structures are required.

What Interviewers Usually Probe

Asks if brute-force enumeration is acceptable given small constraints.
Checks understanding of absolute difference and triplet conditions.
Watches for correct index ordering to prevent miscounting.

Common Pitfalls or Variants

Common pitfalls

Using <= instead of < for indices, causing duplicates or invalid triplets.
Neglecting one of the three absolute difference conditions.
Overcomplicating with unnecessary data structures when direct enumeration suffices.

Follow-up variants

Count good quadruplets with four absolute difference conditions.
Find maximum sum of good triplets instead of count.
Restrict triplets to unique values in the array.

FAQ

What is the best approach to solve Count Good Triplets?

Directly enumerate all triplets i < j < k and check the three absolute difference conditions. With small constraints, brute-force works efficiently.

Can I optimize beyond brute-force for large arrays?

For larger arrays, techniques like prefix sums or frequency counting may help, but for this problem's size, simple enumeration is sufficient.

Why do I need to check all three absolute differences?

Each condition filters invalid triplets. Missing any condition will overcount, violating the problem's Array plus Enumeration pattern.

How does index ordering affect the solution?

Indices must satisfy i < j < k; swapping indices or allowing equality can count invalid triplets, leading to wrong results.

Does GhostInterview provide automatic triplet validation?

Yes, it highlights which triplets pass or fail conditions and ensures all enumerated combinations are accurately counted.

terminal

Solution

Solution 1: Enumeration

We can enumerate all $i$, $j$, and $k$ where $i \lt j \lt k$, and check if they simultaneously satisfy $|\textit{arr}[i] - \textit{arr}[j]| \le a$, $|\textit{arr}[j] - \textit{arr}[k]| \le b$, and $|\textit{arr}[i] - \textit{arr}[k]| \le c$. If they do, we increment the answer by one.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#1566 detect pattern of length m repeated k or more times #1601 maximum number of achievable transfer requests #1620 coordinate with maximum network quality