Count Good Triplets
EasyPrompt
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]| <= c
Where |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 <= 1000
Approaches
2 approaches with complexity analysis and trade-offs.
This is the most straightforward and intuitive approach. It involves using three nested loops to iterate through all possible triplets of indices (i, j, k) that satisfy the condition 0 <= i < j < k < arr.length. For each valid triplet of indices, it checks if the corresponding values in the array satisfy the three absolute difference conditions. If all conditions are met, a counter is incremented.
Algorithm
- Initialize a counter
countto 0. - Iterate through the array with a variable
ifrom0tolength - 3. - Inside this loop, iterate with a variable
jfromi + 1tolength - 2. - Inside this second loop, check if
|arr[i] - arr[j]| <= a. If not, you can continue to the nextjto optimize slightly. - If the first condition holds, iterate with a variable
kfromj + 1tolength - 1. - Check if the remaining two conditions,
|arr[j] - arr[k]| <= band|arr[i] - arr[k]| <= c, are met. - If all three conditions are met, increment
count. - After the loops complete, return
count.
Walkthrough
The algorithm iterates through every possible combination of three distinct indices i, j, and k from the array, ensuring that i < j < k. This is achieved using three nested loops.
- The outer loop picks the first element,
arr[i], iteratingifrom0ton-3. - The middle loop picks the second element,
arr[j], iteratingjfromi+1ton-2. - The inner loop picks the third element,
arr[k], iteratingkfromj+1ton-1.
Inside the innermost loop, we have a unique triplet (arr[i], arr[j], arr[k]). We then check if this triplet is "good" by verifying the three given conditions:
|arr[i] - arr[j]| <= a|arr[j] - arr[k]| <= b|arr[i] - arr[k]| <= c
If all three conditions hold true, we increment a counter variable. After all possible triplets have been checked, the final value of the counter is the answer.
class Solution { public int countGoodTriplets(int[] arr, int a, int b, int c) { int n = arr.length; int count = 0; for (int i = 0; i < n - 2; i++) { for (int j = i + 1; j < n - 1; j++) { if (Math.abs(arr[i] - arr[j]) <= a) { for (int k = j + 1; k < n; k++) { if (Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) { count++; } } } } } return count; }}Complexity
Time
O(n^3), where `n` is the length of the array `arr`. This is because of the three nested loops that iterate through all possible triplets.
Space
O(1), as we only use a constant amount of extra space for the counter and loop variables.
Trade-offs
Pros
Very simple to understand and implement.
Requires no additional space beyond a few variables for loops and counting.
For the given constraints (
n <= 100), this approach is fast enough to pass.
Cons
The cubic time complexity makes this approach inefficient for larger input sizes (e.g., if
nwere greater than a few hundred).
This approach improves upon the brute-force method by using a Fenwick Tree (also known as a Binary Indexed Tree or BIT) to optimize the counting process. Instead of a third loop to find k, we can restructure the loops to fix j and k and then efficiently count the number of valid i's. This reduces the time complexity from cubic to quadratic.
Algorithm
- Initialize
count = 0and a Fenwick Treeftof sizemaxValue + 1(wheremaxValueis 1000). - Iterate
jfrom1ton-2(wherenis the array length). - Before the inner loop for
k, update the Fenwick Tree with the element atj-1:ft.update(arr[j-1], 1). This makes the frequency counts of elements at indices less thanjavailable for querying. - Start an inner loop for
kfromj+1ton-1. - Inside the
kloop, first check if|arr[j] - arr[k]| <= b. - If it's true, calculate the valid range
[low, high]forarr[i]based onarr[j],arr[k],a, andc. - Query the Fenwick Tree for the number of elements in this range:
ft.queryRange(low, high). - Add the result of the query to the total
count. - After both loops complete, return
count.
Walkthrough
The core idea is to iterate through the middle index j and the last index k of the triplet, and for each pair (j, k), efficiently count the number of valid first indices i (where i < j).
We loop j from 1 to n-2. For each j, we maintain a data structure that stores the frequencies of values in arr[0...j-1]. A Fenwick Tree is ideal for this as it allows for efficient updates and range sum queries. The values in arr are up to 1000, so the Fenwick Tree will be of size 1001.
As we iterate j from 1 to n-2, we do the following:
- Update the Fenwick Tree with
arr[j-1]. Now the tree contains the frequency distribution of all elements with indices less thanj. - Start an inner loop for
kfromj+1ton-1. - For the pair
(j, k), if|arr[j] - arr[k]| <= b, we need to counti < jsuch that|arr[i] - arr[j]| <= aand|arr[i] - arr[k]| <= c. These two conditions define a valid range for the value ofarr[i]:[max(arr[j]-a, arr[k]-c), min(arr[j]+a, arr[k]+c)]. - We query our Fenwick Tree for the number of elements in this calculated range. This query, which takes
O(log V)time (whereVis the maximum value), gives us the number of validi's for the currentjandk. - This count is added to our total result.
This method avoids the third linear scan, replacing it with a logarithmic time query, thus improving the overall time complexity.
class FenwickTree { private int[] bit; private int size; public FenwickTree(int size) { this.size = size; this.bit = new int[size + 1]; } public void update(int index, int delta) { index++; // 1-based index while (index <= size) { bit[index] += delta; index += index & -index; } } public int query(int index) { if (index < 0) return 0; index++; // 1-based index int sum = 0; while (index > 0) { sum += bit[index]; index -= index & -index; } return sum; } public int queryRange(int left, int right) { if (left > right) { return 0; } return query(right) - query(left - 1); }} class Solution { public int countGoodTriplets(int[] arr, int a, int b, int c) { int n = arr.length; if (n < 3) return 0; int count = 0; int maxValue = 1000; FenwickTree ft = new FenwickTree(maxValue + 1); // ft will store counts of elements arr[0...j-1] for (int j = 1; j < n - 1; j++) { // Update ft with arr[j-1] to include it in the counts for i < j ft.update(arr[j-1], 1); for (int k = j + 1; k < n; k++) { if (Math.abs(arr[j] - arr[k]) <= b) { // Count i < j such that: // |arr[i] - arr[j]| <= a => arr[j]-a <= arr[i] <= arr[j]+a // |arr[i] - arr[k]| <= c => arr[k]-c <= arr[i] <= arr[k]+c int low = Math.max(arr[j] - a, arr[k] - c); int high = Math.min(arr[j] + a, arr[k] + c); low = Math.max(0, low); high = Math.min(maxValue, high); count += ft.queryRange(low, high); } } } return count; }}Complexity
Time
O(n^2 * logV), where `n` is the length of the array and `V` is the range of values in the array. The two nested loops for `j` and `k` run in O(n^2), and each Fenwick Tree query takes O(logV) time.
Space
O(V), where `V` is the maximum possible value in the array (1001 in this case). This space is used for the Fenwick Tree.
Trade-offs
Pros
More efficient than the brute-force approach, with a time complexity of O(n^2 * logV).
The space complexity of O(V) is efficient as it does not depend on the input size
n.
Cons
More complex to understand and implement compared to the brute-force solution.
The overhead of the data structure might make it slightly slower than the brute-force approach for very small
n, although its asymptotic complexity is better.
Solutions
Solution
public class Solution { public int CountGoodTriplets(int[] arr, int a, int b, int c) { int n = arr.Length; int ans = 0; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { if (Math.Abs(arr[i] - arr[j]) <= a && Math.Abs(arr[j] - arr[k]) <= b && Math.Abs(arr[i] - arr[k]) <= c) { ++ans; } } } } return ans; }}class Solution { public int countGoodTriplets ( int [] arr , int a , int b , int c ) { int n = arr . length ; int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = i + 1 ; j < n ; ++ j ) { for ( int k = j + 1 ; k < n ; ++ k ) { if ( Math . abs ( arr [ i ] - arr [ j ]) <= a && Math . abs ( arr [ j ] - arr [ k ]) <= b && Math . abs ( arr [ i ] - arr [ k ]) <= c ) { ++ ans ; } } } } return ans ; } }class Solution { public: int countGoodTriplets ( vector < int >& arr , int a , int b , int c ) { int n = arr . size (); int ans = 0 ; for ( int i = 0 ; i < n ; ++ i ) { for ( int j = i + 1 ; j < n ; ++ j ) { for ( int k = j + 1 ; k < n ; ++ k ) { ans += abs ( arr [ i ] - arr [ j ]) <= a && abs ( arr [ j ] - arr [ k ]) <= b && abs ( arr [ i ] - arr [ k ]) <= c ; } } } return ans ; } };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 ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.