Skip to main content

Count Good Triplets Solution

In this page, we will solve the Count Good Triplets problem using multiple approaches: brute-force and optimization. We will provide the implementation of the solution in Python, JavaScript, TypeScript, Java, and C++.

Problem 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])(arr[i], arr[j], arr[k]) is good if the following conditions are true:

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

Where ∣x∣|x| denotes the absolute value of x.

Return the number of good triplets.

Examples​

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

Solution for Count Good Triplets Problem​

Intuition and Approach​

The problem can be solved using different approaches. We will start with a brute-force approach and then look at an optimized approach using early exits to reduce unnecessary comparisons.

Approach 1: Brute Force​

We iterate through all possible triplets (i, j, k) where 0 <= i < j < k < arr.length and check if they satisfy the conditions |arr[i] - arr[j]| <= a, |arr[j] - arr[k]| <= b, and |arr[i] - arr[k]| <= c. If they do, we count it as a good triplet.

Implementation​

Live Editor
function countGoodTriplets() {
  const arr = [3, 0, 1, 1, 9, 7];
  const a = 7;
  const b = 2;
  const c = 3;

  const countGoodTriplets = function(arr, a, b, c) {
    let count = 0;
    for (let i = 0; i < arr.length - 2; i++) {
      for (let j = i + 1; j < arr.length - 1; j++) {
        if (Math.abs(arr[i] - arr[j]) > a) continue;
        for (let k = j + 1; k < arr.length; k++) {
          if (Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
            count++;
          }
        }
      }
    }
    return count;
  };

  const result = countGoodTriplets(arr, a, b, c);
  return (
    <div>
      <p>
        <b>Input:</b> arr = {JSON.stringify(arr)}, a = {a}, b = {b}, c = {c}
      </p>
      <p>
        <b>Output:</b> {result}
      </p>
    </div>
  );
}
Result
Loading...

Codes in Different Languages​

Written by @manishh12
 function countGoodTriplets(arr, a, b, c) {
let count = 0;
for (let i = 0; i < arr.length - 2; i++) {
for (let j = i + 1; j < arr.length - 1; j++) {
for (let k = j + 1; k < arr.length; k++) {
if (Math.abs(arr[i] - arr[j]) <= a &&
Math.abs(arr[j] - arr[k]) <= b &&
Math.abs(arr[i] - arr[k]) <= c) {
count++;
}
}
}
}
return count;
}

Complexity Analysis​

  • Time Complexity: O(n3)O(n^3)
  • Space Complexity: O(1)O(1)
  • Where n is the length of the array arr.
  • The time complexity is determined by the three nested loops iterating through the array.
  • The space complexity is constant as no additional space is required beyond a few variables.
Note

By using these approaches, we can efficiently solve the Count Good Triplets problem for the given constraints.

References​