Jobs

Interviews

Discussions

Count Good Triplets

Easy

Asked by:

16 views

Topics:

Arrays

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 <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000

Try coding it in LeetCode

Count Good Triplets

Easy

Asked by:

16 views

Topics:

Arrays

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 <= 100
0 <= arr[i] <= 1000
0 <= a, b, c <= 1000

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `arr` and the maximum value for `a`, `b`, and `c`?
Can the input array `arr` contain duplicate values, and if so, should each distinct triplet be counted, or should triplets with the same values at different indices be counted multiple times?
Are the values `a`, `b`, and `c` non-negative integers?
If no 'good' triplets exist, what should the function return?
Is the order of the elements within a triplet important (e.g., is (arr[i], arr[j], arr[k]) considered different from (arr[k], arr[j], arr[i]) if i != k)? Assume i < j < k.

Brute Force Solution

Approach

The goal is to find all the 'good' combinations of three numbers from a larger set. A brute force approach simply checks every possible combination of three numbers to see if it meets the 'good' criteria.

Here's how the algorithm would work step-by-step:

Take the first number in the set.
Pair it with every possible second number that comes after it in the set.
For each of these pairs, add every possible third number that comes after the second number in the set.
For each combination of three numbers, check if it's a 'good' triplet according to the given rules.
If the combination meets the criteria, count it as a 'good' triplet.
Repeat this process, starting with the second number as the first number, then the third, and so on, until all possible combinations have been checked.
The final count is the total number of 'good' triplets found.

Code Implementation

def count_good_triplets_brute_force(arr, a_threshold, b_threshold, c_threshold):
    good_triplet_count = 0

    for first_index in range(len(arr)): 
        for second_index in range(first_index + 1, len(arr)): 
            # Iterate over all elements after the first one.
            for third_index in range(second_index + 1, len(arr)): 
                # Iterate over all elements after the second one.
                if abs(arr[first_index] - arr[second_index]) <= a_threshold: 

                    if abs(arr[second_index] - arr[third_index]) <= b_threshold:
                        # Ensure the first two conditions are true.

                        if abs(arr[first_index] - arr[third_index]) <= c_threshold:
                            # Check the final condition.
                            good_triplet_count += 1

    return good_triplet_count

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through all possible triplets in the input array of size n. The outermost loop considers each element as the first element of a potential triplet. The second loop considers each subsequent element as the second element, and the innermost loop considers each element after that as the third. Therefore, the algorithm effectively checks all combinations of three elements, leading to a number of operations proportional to n * n * n, which simplifies to O(n^3).

Space Complexity

O(1) – The provided algorithm iterates through the input array using nested loops to find triplets. It does not create any additional data structures like lists, maps, or sets to store intermediate results or track visited elements. The only memory used is for a few integer variables to store indices and the count of good triplets, which takes constant space regardless of the input array size N. Thus, the space complexity is O(1).

Optimal Solution

Approach

The basic idea is to efficiently count valid combinations by focusing on the relationships between the numbers and pre-calculating information to avoid repeated checks. We'll build upon our knowledge as we progress through the list of numbers to reduce the overall work.

Here's how the algorithm would work step-by-step:

Consider the first number in the list. We will use this number to potentially form the first part of a triplet.
For each subsequent number in the list, we check if the difference between it and the first number satisfies the first condition. If it does not, move on to the next number. If it does, we continue to consider this potential pair.
Now, for each number that comes after the second number, check if the difference between it and the first number AND the difference between it and the second number satisfy their respective conditions. If both conditions are met, and the final condition between the second number and third number is also met, then we have found a valid triplet.
Keep a running count of all valid triplets found.
Repeat this process, starting with the second number in the original list, and continuing until you have considered each number as the first number of a potential triplet.
The final count represents the total number of "good" triplets in the list.

Code Implementation

def count_good_triplets(arr, a, b, c):
    number_of_good_triplets = 0
    array_length = len(arr)

    for first_index in range(array_length):
        for second_index in range(first_index + 1, array_length):
            # Only proceed if condition between first and second elements is met.
            if abs(arr[first_index] - arr[second_index]) <= a:

                for third_index in range(second_index + 1, array_length):
                    # Checking all three conditions to identify a good triplet
                    if abs(arr[first_index] - arr[third_index]) <= b and abs(arr[second_index] - arr[third_index]) <= c:
                        number_of_good_triplets += 1

    # Return the total count of good triplets
    return number_of_good_triplets

Big(O) Analysis

Time Complexity

O(n^3) – The algorithm iterates through each number in the input array of size n, potentially using it as the first element of a triplet. For each of these numbers, it then iterates through the remaining numbers to potentially form the second element of the triplet. Finally, for each potential pair, it iterates through the numbers after the second element to find a potential third element. Thus, we have three nested loops each potentially iterating up to n times, leading to O(n*n*n) complexity. This simplifies to O(n^3).

Space Complexity

O(1) – The provided solution outline focuses on iterative traversal and comparison of elements within the input array. No auxiliary data structures, such as temporary arrays, hash maps, or recursion, are explicitly mentioned for storing intermediate results or tracking visited elements. The algorithm primarily utilizes a few integer variables (such as counters or indices) that occupy a constant amount of memory regardless of the input array's size N. Therefore, the auxiliary space complexity is constant.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0, as there are no triplets to count.
Array size less than 3	Return 0, as a triplet requires at least three elements.
Large array size causing potential performance issues (Time Limit Exceeded)	Optimize the solution using techniques like early exit or a sliding window if possible to reduce the number of comparisons.
Integer overflow in calculations if array values are very large and a, b, c are large	Use a data type that can accommodate larger numbers, like long, to prevent overflow during absolute difference calculations.
All elements in the array are identical, and the difference constraints are met.	Handle the combinatorial explosion correctly to avoid counting the same triplet multiple times, possibly using combinations formula.
Extreme boundary values for a, b, and c (e.g., a, b, c are very small, or very large).	Ensure the absolute difference calculation does not result in unexpected behavior or errors due to boundary conditions.
No good triplets exist in the array given the constraints.	The solution should correctly return 0 when no triplets satisfy the given conditions.
Array contains negative numbers	The absolute difference function should handle negative numbers correctly ensuring correct counts.

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the maximum size of the input array `arr` and the maximum value for `a`, `b`, and `c`?
Can the input array `arr` contain duplicate values, and if so, should each distinct triplet be counted, or should triplets with the same values at different indices be counted multiple times?
Are the values `a`, `b`, and `c` non-negative integers?
If no 'good' triplets exist, what should the function return?
Is the order of the elements within a triplet important (e.g., is (arr[i], arr[j], arr[k]) considered different from (arr[k], arr[j], arr[i]) if i != k)? Assume i < j < k.

Brute Force Solution

Approach

Here's how the algorithm would work step-by-step:

Take the first number in the set.
Pair it with every possible second number that comes after it in the set.
For each of these pairs, add every possible third number that comes after the second number in the set.
For each combination of three numbers, check if it's a 'good' triplet according to the given rules.
If the combination meets the criteria, count it as a 'good' triplet.
Repeat this process, starting with the second number as the first number, then the third, and so on, until all possible combinations have been checked.
The final count is the total number of 'good' triplets found.

Code Implementation

def count_good_triplets_brute_force(arr, a_threshold, b_threshold, c_threshold):
    good_triplet_count = 0

    for first_index in range(len(arr)): 
        for second_index in range(first_index + 1, len(arr)): 
            # Iterate over all elements after the first one.
            for third_index in range(second_index + 1, len(arr)): 
                # Iterate over all elements after the second one.
                if abs(arr[first_index] - arr[second_index]) <= a_threshold: 

                    if abs(arr[second_index] - arr[third_index]) <= b_threshold:
                        # Ensure the first two conditions are true.

                        if abs(arr[first_index] - arr[third_index]) <= c_threshold:
                            # Check the final condition.
                            good_triplet_count += 1

    return good_triplet_count

Big(O) Analysis

Time Complexity

Space Complexity

Optimal Solution

Approach

Here's how the algorithm would work step-by-step:

Consider the first number in the list. We will use this number to potentially form the first part of a triplet.
For each subsequent number in the list, we check if the difference between it and the first number satisfies the first condition. If it does not, move on to the next number. If it does, we continue to consider this potential pair.
Now, for each number that comes after the second number, check if the difference between it and the first number AND the difference between it and the second number satisfy their respective conditions. If both conditions are met, and the final condition between the second number and third number is also met, then we have found a valid triplet.
Keep a running count of all valid triplets found.
Repeat this process, starting with the second number in the original list, and continuing until you have considered each number as the first number of a potential triplet.
The final count represents the total number of "good" triplets in the list.

Code Implementation

def count_good_triplets(arr, a, b, c):
    number_of_good_triplets = 0
    array_length = len(arr)

    for first_index in range(array_length):
        for second_index in range(first_index + 1, array_length):
            # Only proceed if condition between first and second elements is met.
            if abs(arr[first_index] - arr[second_index]) <= a:

                for third_index in range(second_index + 1, array_length):
                    # Checking all three conditions to identify a good triplet
                    if abs(arr[first_index] - arr[third_index]) <= b and abs(arr[second_index] - arr[third_index]) <= c:
                        number_of_good_triplets += 1

    # Return the total count of good triplets
    return number_of_good_triplets

Big(O) Analysis

Time Complexity

Space Complexity

Edge Cases

Case	How to Handle
Empty or null input array	Return 0, as there are no triplets to count.
Array size less than 3	Return 0, as a triplet requires at least three elements.
Large array size causing potential performance issues (Time Limit Exceeded)	Optimize the solution using techniques like early exit or a sliding window if possible to reduce the number of comparisons.
Integer overflow in calculations if array values are very large and a, b, c are large	Use a data type that can accommodate larger numbers, like long, to prevent overflow during absolute difference calculations.
All elements in the array are identical, and the difference constraints are met.	Handle the combinatorial explosion correctly to avoid counting the same triplet multiple times, possibly using combinations formula.
Extreme boundary values for a, b, and c (e.g., a, b, c are very small, or very large).	Ensure the absolute difference calculation does not result in unexpected behavior or errors due to boundary conditions.
No good triplets exist in the array given the constraints.	The solution should correctly return 0 when no triplets satisfy the given conditions.
Array contains negative numbers	The absolute difference function should handle negative numbers correctly ensuring correct counts.