Watch 10 video solutions for Count Good Triplets, a easy level problem involving Array, Enumeration. This walkthrough by NeetCodeIO has 11,516 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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]| <= cWhere |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 <= arr.length <= 1000 <= arr[i] <= 10000 <= a, b, c <= 1000Problem Overview: You get an integer array and three thresholds a, b, and c. Count triplets of indices (i, j, k) such that i < j < k and three constraints hold: |arr[i] - arr[j]| ≤ a, |arr[j] - arr[k]| ≤ b, and |arr[i] - arr[k]| ≤ c. The task is purely about enumerating valid index combinations while efficiently filtering out invalid ones.
Approach 1: Brute Force Enumeration (O(n³) time, O(1) space)
The most direct solution checks every possible triplet. Use three nested loops where i runs from 0..n-3, j from i+1..n-2, and k from j+1..n-1. For each combination, compute the three absolute differences and verify they satisfy the constraints. If all conditions hold, increment the result counter. This approach relies only on simple iteration over the array and constant-time arithmetic checks.
Although the time complexity is O(n³), the constraints of the problem keep n small enough that a full enumeration is practical. The implementation is straightforward and often the first version written during interviews to confirm understanding of the conditions.
Approach 2: Optimized Enumeration with Early Pruning (O(n³) worst-case time, O(1) space)
This version keeps the same triple-loop structure but avoids unnecessary work by validating constraints as early as possible. After choosing indices i and j, immediately check |arr[i] - arr[j]| ≤ a. If this fails, skip the entire inner k loop because no triplet starting with that pair can be valid. Only when the first condition passes do you iterate k and test the remaining two constraints.
Inside the k loop, compute |arr[j] - arr[k]| and |arr[i] - arr[k]| and increment the count when both satisfy their limits. This pruning strategy significantly reduces the number of checks in practice, especially when many pairs already violate the first constraint. The technique is a common pattern in enumeration problems: validate cheaper conditions early to shrink the search space.
Recommended for interviews: Start with the brute force explanation because it clearly matches the problem definition and demonstrates correct reasoning about index ordering. Then show the optimized enumeration where the first constraint filters pairs before exploring the third index. Interviewers expect the pruning step since it reduces unnecessary iterations while keeping the implementation simple and readable.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Baseline solution when constraints are small and clarity is preferred |
| Enumeration with Early Pruning | O(n^3) worst case | O(1) | General case; reduces unnecessary checks by filtering invalid (i, j) pairs early |