Count Good Triplets

EASY

Description

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

Approaches

Checkout 2 different approaches to solve Count Good Triplets. Click on different approaches to view the approach and algorithm in detail.

Brute-Force Triple Nested Loop

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 count to 0.
Iterate through the array with a variable i from 0 to length - 3.
Inside this loop, iterate with a variable j from i + 1 to length - 2.
Inside this second loop, check if |arr[i] - arr[j]| <= a. If not, you can continue to the next j to optimize slightly.
If the first condition holds, iterate with a variable k from j + 1 to length - 1.
Check if the remaining two conditions, |arr[j] - arr[k]| <= b and |arr[i] - arr[k]| <= c, are met.
If all three conditions are met, increment count.
After the loops complete, return count.

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], iterating i from 0 to n-3.
The middle loop picks the second element, arr[j], iterating j from i+1 to n-2.
The inner loop picks the third element, arr[k], iterating k from j+1 to n-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 Analysis

Time Complexity: 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 Complexity: O(1), as we only use a constant amount of extra space for the counter and loop variables.

Pros and Cons

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 n were greater than a few hundred).

Code Solutions

Checking out 4 solutions in different languages for Count Good Triplets. Click on different languages to view the code.

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;
    }
}

Video Solution

Watch the video walkthrough for Count Good Triplets

Patterns:

Enumeration

Data Structures:

Array

Companies:

Turvo |