💡 Problem Formulation: A “good triplet” in an array is a set of three different indices (i, j, k), such that 0 ≤ i < j < k < arr.length. Given an integer array arr and two integer variables a, b, and c, a triplet (arr[i], arr[j], arr[k]) is considered good if |arr[i] – arr[j]| <= a, |arr[j] – arr[k]| <= b, and |arr[i] – arr[k]| <= c. The task is to count the number of good triplets. For instance, if the input array is [3, 0, 1, 1, 9, 7] with a = 7, b = 2, and c = 3, the desired output number of good triplets is 4.
Method 1: Brute Force O(n^3) Approach
This method iterates through all possible triplets within the array using three nested loops, each checking the given constraints. While this approach is straightforward and easy to implement, it does not scale well with large arrays due to its cubic time complexity.
Here’s an example:
def count_good_triplets(arr, a, b, c):
count = 0
n = len(arr)
for i in range(n):
for j in range(i+1, n):
for k in range(j+1, n):
if abs(arr[i] - arr[j]) <= a and \
abs(arr[j] - arr[k]) <= b and \
abs(arr[i] - arr[k]) <= c:
count += 1
return count
print(count_good_triplets([3,0,1,1,9,7], 7, 2, 3))
Output: 4
This code snippet defines a function count_good_triplets that takes an array and three integers a, b, and c as arguments. It initializes a counter to zero and iterates over the array using three nested for loops to check every triplet combination. If a triplet satisfies all three conditions, it increments the counter.
Method 2: Optimized Dual Pointer Approach
The dual pointer approach minimizes unnecessary checks by using two pointers to traverse through the array after sorting it. This method dramatically improves performance, especially when the array is large, although it may not be as efficient as more advanced techniques.
Here’s an example:
def count_good_triplets_optimized(arr, a, b, c):
# This method requires a sorted array
arr.sort()
count = 0
n = len(arr)
for i in range(n):
k = i + 2 # Initialize k to the smallest possible value
for j in range(i+1, n):
while k < n and arr[k] - arr[j] <= b:
k += 1
for l in range(j+1, k):
if abs(arr[i] - arr[j]) <= a and abs(arr[i] - arr[l]) <= c:
count += 1
return count
print(count_good_triplets_optimized([3,0,1,1,9,7], 7, 2, 3))
Output: 4
The function count_good_triplets_optimized again takes the array and the a, b, and c variables as input. It starts by sorting the array to make it easier to apply the dual pointer technique. It then iterates over the sorted array with two pointers to find good triplets. When conditions are satisfied, the counter is incremented.
Method 3: Using Binary Search
Binary search can be applied after sorting the array to find the third element of the triplet within the given constraints. This method is more efficient than the brute force method and works well for larger input sizes, but it’s more complex to code.
Here’s an example:
import bisect
def count_good_triplets_binary_search(arr, a, b, c):
arr.sort()
count = 0
for i in range(len(arr)):
for j in range(i+1, len(arr)):
# Binary search for the range of k
k_left = bisect.bisect_left(arr, arr[j] - b)
k_right = bisect.bisect_right(arr, arr[i] + c)
count += max(0, min(len(arr), k_right) - max(i+2, k_left))
return count
print(count_good_triplets_binary_search([3,0,1,1,9,7], 7, 2, 3))
Output: 4
The count_good_triplets_binary_search function uses the Python library bisect to perform binary searches on the sorted array arr. The function finds indices where the third element of the triplet may be located that satisfy the given constraints. This method uses the bisect_left and bisect_right functions to quickly identify the range of valid k indices for each pair (i, j).
Method 4: Hash Map to Reduce Redundancy
Using a hash map to store the results of comparisons can avoid redundant computations, particularly useful when the array contains many duplicate elements. This method can provide speedups but would increase memory usage compared to the other methods.
Here’s an example:
def count_good_triplets_hash_map(arr, a, b, c):
count = 0
seen = {}
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if (arr[i], arr[j]) not in seen:
seen[(arr[i], arr[j])] = abs(arr[i] - arr[j]) <= a
if seen[(arr[i], arr[j])]:
for k in range(j+1, len(arr)):
if abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c:
count += 1
return count
print(count_good_triplets_hash_map([3,0,1,1,9,7], 7, 2, 3))
Output: 4
The function count_good_triplets_hash_map utilizes a dictionary seen to cache the results of comparisons between elements i and j. If the result is not in the hash map, the absolute difference is computed and stored. The presence of previous (i, j) computations in the map prevents recalculation, potentially saving time on larger inputs.
Bonus One-Liner Method 5: Python List Comprehension
Python’s list comprehensions can be used to condense the brute force approach into a one-liner. While this method is elegant and concise for small datasets, it offers no performance advantage over the unoptimized brute force method.
Here’s an example:
def count_good_triplets_oneliner(arr, a, b, c):
return sum(1 for i in range(len(arr)) for j in range(i+1, len(arr))
for k in range(j+1, len(arr))
if abs(arr[i] - arr[j]) <= a and abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c)
print(count_good_triplets_oneliner([3,0,1,1,9,7], 7, 2, 3))
Output: 4
This one-liner count_good_triplets_oneliner relies on Python’s list comprehension feature to iterate over indices i, j, and k, and checks the triplet constraints inline, incrementing the sum for every good triplet found.
Summary/Discussion
- Method 1: Brute Force O(n^3) Approach. Simple to understand and implement. Performance is poor for large datasets due to cubic time complexity.
- Method 2: Optimized Dual Pointer Approach. Offers better performance than brute force. Still not as efficient as more advanced algorithms for very large datasets.
- Method 3: Using Binary Search. More efficient than brute force for larger datasets. Complexity of implementation is higher, especially with binary search logic.
- Method 4: Hash Map to Reduce Redundancy. Can provide performance boosts in cases with many duplicates. Increased memory usage due to caching of results.
- Method 5: Python List Comprehension. Elegant one-liner. Offers no performance benefits over brute force and lacks readability for complex operations.