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 <= 1000The goal in #1534 Count Good Triplets is to count index triplets (i, j, k) such that i < j < k and three absolute difference constraints are satisfied. Because the input size is relatively small, a direct enumeration approach works effectively.
Iterate through all possible combinations of three indices using nested loops while maintaining the ordering constraint. For each candidate triplet, check whether |arr[i] - arr[j]| ≤ a, |arr[j] - arr[k]| ≤ b, and |arr[i] - arr[k]| ≤ c. If all conditions hold, increment the count. Since the array size is limited, this straightforward method remains efficient and easy to implement.
The main idea is systematic exploration of valid index combinations while applying the constraints early to avoid unnecessary checks. The typical implementation runs in O(n³) time with O(1) extra space, which is acceptable for the given constraints.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Triple Loop Enumeration | O(n^3) | O(1) |
NeetCodeIO
Use these hints if you're stuck. Try solving on your own first.
Notice that the constraints are small enough for a brute force solution to pass.
Loop through all triplets, and count the ones that are good.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Enumeration is used because we must consider combinations of three indices that satisfy multiple conditions. Given the small input size, iterating through all possible triplets ensures correctness without requiring complex optimizations.
Problems like Count Good Triplets are common in coding interviews to test understanding of brute-force enumeration and constraint checking. They also help evaluate a candidate's ability to reason about time complexity and loop ordering.
No special data structure is required for this problem. A simple array traversal with nested loops works well because the constraints are small and the task mainly involves checking conditions between elements.
The common approach is to enumerate all possible triplets using three nested loops while maintaining i < j < k. For each triplet, check the three absolute difference conditions. Because the array size is small, this O(n^3) approach is efficient enough.