We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Count Good Triplets

Number: 1656

Difficulty: Easy

Paid? No

Companies: Apple, Turvo

Problem Description

Given an array of integers and three integers a, b, and c, count the number of triplets (arr[i], arr[j], arr[k]) that satisfy:

  • 0 <= i < j < k < arr.length
  • |arr[i] - arr[j]| <= a
  • |arr[j] - arr[k]| <= b
  • |arr[i] - arr[k]| <= c

Key Insights

  • Brute force approach using three nested loops is acceptable since the maximum array length is 100.
  • Check all possible triplets and count only those meeting the specified conditions.
  • Absolute difference comparisons are the key condition validations.

Space and Time Complexity

Time Complexity: O(n^3) where n is the length of the array. Space Complexity: O(1) extra space (ignoring input space).

Solution

We use a brute force algorithm with three nested loops, iterating over all combinations of triplets (i, j, k) ensuring i < j < k. For each triplet, we calculate the absolute differences:

  • |arr[i] - arr[j]|
  • |arr[j] - arr[k]|
  • |arr[i] - arr[k]| The triplet is counted as good if all absolute differences satisfy the conditions (<= a, <= b, and <= c respectively). This simple approach leverages the small input size, eliminating the need for more complex data structures or optimizations.

Code Solutions

# Python solution for Count Good Triplets
def countGoodTriplets(arr, a, b, c):
    # Initialize counter for good triplets
    good_triplets_count = 0
    n = len(arr)
    # Iterate over all triplet combinations with indices i, j, k where i < j < k
    for i in range(n):
        for j in range(i + 1, n):
            for k in range(j + 1, n):
                # Check if absolute differences satisfy the conditions
                if abs(arr[i] - arr[j]) <= a and abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c:
                    good_triplets_count += 1
    # Return the count of good triplets
    return good_triplets_count

# Example usage:
arr = [3, 0, 1, 1, 9, 7]
a, b, c = 7, 2, 3
print(countGoodTriplets(arr, a, b, c))  # Expected output: 4
← Back to All Questions