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 brute force approach involves using three nested loops, iterating over all possible combinations of indices (i, j, k) with the condition i < j < k. For each triplet, we check if the given conditions |arr[i] - arr[j]| <= a, |arr[j] - arr[k]| <= b, and |arr[i] - arr[k]| <= c hold true. If they do, we increment the count of good triplets.
This C solution follows a straightforward brute force approach using three nested loops. It iterates over all the indices i, j, and k such that 0 <= i < j < k < arr.size. For each such combination, it checks if all given conditions are satisfied.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^3), where n is the array's length due to three nested loops. Space Complexity: O(1), only basic variables are used.
This approach also uses three nested loops, but incorporates early stopping by breaking out of the inner loops if the conditions become unsatisfiable. This reduces unnecessary iterations and slightly optimizes the solution in practical scenarios.
This C solution enhances the brute force logic with early exits from loops if the condition of a particular segment fails (e.g., exits j-loop if |arr[i] - arr[j]| > a).
C++
Java
Python
C#
JavaScript
Time Complexity: Still O(n^3) in the worst case but can be faster in practice due to early breaks. Space Complexity: O(1).
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3), where n is the array's length due to three nested loops. Space Complexity: O(1), only basic variables are used. |
| Optimized Combination with Early Break | Time Complexity: Still O(n^3) in the worst case but can be faster in practice due to early breaks. Space Complexity: O(1). |
Count Good Triplets - Leetcode 1534 - Python • NeetCodeIO • 8,623 views views
Watch 9 more video solutions →Practice Count Good Triplets with our built-in code editor and test cases.
Practice on FleetCode