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

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 <= 100$
• $0 <= arr[i] <= 1000$
• $0 <= 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.

• Brute Force
• Optimized Brute Force

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

JavaScript

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

TypeScript

Written by @manishh12

 function countGoodTriplets(arr: number[], a: number, b: number, c: number): number {
   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;
 }

Python

Written by @manishh12

 class Solution:
     def countGoodTriplets(self, arr: List[int], a: int, b: int, c: int) -> int:
         count = 0
         for i in range(len(arr) - 2):
             for j in range(i + 1, len(arr) - 1):
                 for k in range(j + 1, len(arr)):
                     if abs(arr[i] - arr[j]) <= a and abs(arr[j] - arr[k]) <= b and abs(arr[i] - arr[k]) <= c:
                         count += 1
         return count

Java

Written by @manishh12

 class Solution {
     public int countGoodTriplets(int[] arr, int a, int b, int c) {
         int count = 0;
         for (int i = 0; i < arr.length - 2; i++) {
             for (int j = i + 1; j < arr.length - 1; j++) {
                 for (int 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;
     }
 }

C++

Written by @manishh12

 class Solution {
 public:
     int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
         int count = 0;
         for (int i = 0; i < arr.size() - 2; i++) {
             for (int j = i + 1; j < arr.size() - 1; j++) {
                 for (int k = j + 1; k < arr.size(); k++) {
                     if (abs(arr[i] - arr[j]) <= a &&
                         abs(arr[j] - arr[k]) <= b &&
                         abs(arr[i] - arr[k]) <= c) {
                         count++;
                     }
                 }
             }
         }
         return count;
     }
 };

Complexity Analysis

• Time Complexity: $O(n^3)$
• Space Complexity: $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

• LeetCode Problem: LeetCode Problem
• Solution Link: Count Good Triplets Solution on LeetCode
• Authors LeetCode Profile: Manish Kumar Gupta