Scale Engineer

Count Good Triplets

Easy
#1413Time: 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: O(1), as we only use a constant amount of extra space for the counter and loop variables.1 company
Patterns
Enumeration
Data structures
Array
Companies
Turvo

Prompt

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

2 approaches with complexity analysis and trade-offs.

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.

Walkthrough

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:

  1. |arr[i] - arr[j]| <= a
  2. |arr[j] - arr[k]| <= b
  3. |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

Time

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

O(1), as we only use a constant amount of extra space for the counter and loop variables.

Trade-offs

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).

Solutions

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 walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next →

Next problem