1534. Count Good Triplets
Model: qwen2.5-coder:14b
Topics: Array
FAANG asked: 0
Acceptance rate: 80.3%
Problem Breakdown
The problem requires us to count the number of “good” triplets in an array arr. A triplet (arr[i], arr[j], arr[k]) is considered good if it satisfies three conditions:
0 <= i < j < k < arr.length|arr[i] - arr[j]| <= a|arr[j] - arr[k]| <= b|arr[i] - arr[k]| <= c
Inputs:
- An array of integers
arr. - Three integers
a,b, andc.
Outputs:
- The number of good triplets.
Implicit Constraints or Edge Cases:
- The array length is between 3 and 100.
- Array elements are between 0 and 1000.
a,b, andcare non-negative integers up to 1000.- The array can contain duplicate values.
Intuition
The brute-force approach would involve checking all possible triplets (i, j, k) where 0 <= i < j < k < arr.length. For each triplet, we would verify if it satisfies the three conditions. This approach has a time complexity of (O(n^3)), which is inefficient given the constraints.
A better approach involves iterating through all possible pairs (i, j) and then checking for valid k values that satisfy the conditions with respect to both arr[i] and arr[j]. This reduces the number of checks needed and optimizes the solution.
Approach
- Initialize a counter
good_triplets_countto zero. - Iterate through all possible pairs
(i, j)where0 <= i < j < arr.length. - For each pair
(i, j), check if|arr[i] - arr[j]| <= a. If not, skip to the next pair. - For valid pairs
(i, j), iterate through all possiblekvalues wherej < k < arr.length. - Check if both
|arr[j] - arr[k]| <= band|arr[i] - arr[k]| <= care satisfied. - If the conditions are met, increment the
good_triplets_count. - Return the
good_triplets_count.
Complexity Analysis
-
Time Complexity: (O(n^2))
- We iterate through all pairs
(i, j)which takes (O(n^2)) time. - For each pair, we check valid
kvalues, which in the worst case is (O(n)), but on average will be much less due to the constraints.
- We iterate through all pairs
-
Space Complexity: (O(1))
- We use a constant amount of extra space for variables and counters.
Solution
def countGoodTriplets(arr, a, b, c):
good_triplets_count = 0
n = len(arr)
for i in range(n - 2):
for j in range(i + 1, n - 1):
if abs(arr[i] - arr[j]) <= a:
for k in range(j + 1, n):
if abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c:
good_triplets_count += 1
return good_triplets_count
Edge Cases Handled
- All elements are the same: The code will correctly count triplets where all elements are equal, as long as they satisfy the conditions.
- No valid triplets exist: If no triplet satisfies the conditions, the function returns 0.
- Array length is exactly 3: The function handles this by iterating through all possible triplets without any issues.