Count Good Triplets

Easy
263.

Count Good Triplets

Count Good Triplets is an easy coding problem on arrays and enumeration, asked in Amazon and Adobe interviews.

Given an array of integers arr and three integers a, b and c, count the good triplets.

A triplet (arr[i], arr[j], arr[k]) is good when 0 <= i < j < k < arr.length and all three hold:

  • abs(arr[i] - arr[j]) <= a
  • abs(arr[j] - arr[k]) <= b
  • abs(arr[i] - arr[k]) <= c

Example 1

Input
arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output
4

Example 2

Input
arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output
0

Example 3

Input
arr = [1,1,1], a = 0, b = 0, c = 0
Output
1

Constraints

  • 3 <= arr.length <= 15
  • 0 <= arr[i] <= 1000
  • 0 <= a, b, c <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} arr
 * @param {number} a
 * @param {number} b
 * @param {number} c
 * @return {number}
 */
var countGoodTriplets = function(arr, a, b, c) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Count Good Triplets — Solution in Python, Java & C++

Count Good Triplets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Count Good Triplets is an easy coding problem on arrays and enumeration, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Enumeration
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Given an array of integers arr and three integers a, b and c, count the good triplets.

A triplet (arr[i], arr[j], arr[k]) is good when 0 <= i < j < k < arr.length and all three hold:

  • abs(arr[i] - arr[j]) <= a
  • abs(arr[j] - arr[k]) <= b
  • abs(arr[i] - arr[k]) <= c

Example 1

Input: arr = [3,0,1,1,9,7], a = 7, b = 2, c = 3
Output: 4

Example 2

Input: arr = [1,1,2,2,3], a = 0, b = 0, c = 1
Output: 0

Example 3

Input: arr = [1,1,1], a = 0, b = 0, c = 0
Output: 1

Constraints

  • 3 <= arr.length <= 15
  • 0 <= arr[i] <= 1000
  • 0 <= a, b, c <= 1000

Hints for Count Good Triplets

  1. Hint 1

    The array is small enough that the triple loop is intended.

  2. Hint 2

    Check the i, j condition in the middle loop and skip early — that prunes most of the inner loop's work.

How to solve Count Good Triplets

The array is tiny, so enumerate all i < j < k, but check the (i, j) condition in the middle loop to skip most of the innermost work.

Approach

  1. For each i < j, skip unless |arr[i] - arr[j]| <= a.
  2. For each k > j, count if |arr[j] - arr[k]| <= b and |arr[i] - arr[k]| <= c.

Why it works

Every triple is examined once and only counted when all three constraints hold; the early continue is a constant-factor pruning, not a change in correctness.

Complexity

  • Time — O(n³)
  • Space — O(1)

Pitfalls

  • The constraints (n <= 100) are what make the cubic loop acceptable.

Reference solution

Python

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

Java

public static int countGoodTriplets(int[] arr, int a, int b, int c) {
    int n = arr.length;
    int count = 0;
    for (int i = 0; i < n; i++) {
        for (int j = i + 1; j < n; j++) {
            if (Math.abs(arr[i] - arr[j]) > a) continue;
            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;
}

C++

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

JavaScript

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

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays