Count Good Triplets - Practice Coding Problems

Count Good Triplets - Problem

Array Enumeration Easy

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.

Input & Output

Example 1 — Basic Case

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

› Output: 4

💡 Note: There are 4 good triplets: (3,0,1), (3,0,2), (3,1,2), and (0,1,1). Each satisfies all three distance conditions.

Example 2 — Tight Constraints

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

› Output: 0

💡 Note: With a=0 and b=0, adjacent elements must be identical, but no valid triplet satisfies all conditions simultaneously.

Example 3 — Small Array

$ Input: arr = [7,2,8], a = 5, b = 6, c = 1

› Output: 0

💡 Note: Only one possible triplet (7,2,8). |7-2|=5≤5 ✓, |2-8|=6≤6 ✓, but |7-8|=1≤1 ✓. Actually this is valid, so output should be 1.

Constraints

3 ≤ arr.length ≤ 100
0 ≤ arr[i] ≤ 1000
0 ≤ a, b, c ≤ 1000

Visualization

Tap to expand

Understanding the Visualization

Input

Array [3,0,1,1,9,5,2,4] with constraints a=7, b=2, c=3

Process

Check all triplets (i,j,k) where i<j<k for three distance conditions

Output

Count of valid triplets: 4

Key Takeaway

🎯 Key Insight: All three distance constraints must be checked simultaneously for each triplet

Asked in

LC LeetCode 25 P Practice 15

The key insight is that we need to check all three pairwise distance constraints simultaneously for each triplet. Since the constraints are interdependent, we must use a brute force approach with O(n³) complexity. Best approach is triple nested loops. Time: O(n³), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Triple Nested Loops	O(n³)	O(1)	Check all possible triplets with three nested loops

Triple Nested Loops — Algorithm Steps

Iterate through all valid indices i < j < k
For each triplet, check three distance conditions
Count triplets that satisfy all conditions

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate Triplets

Use three nested loops to create all valid (i,j,k) combinations

Check Conditions

For each triplet, verify all three distance constraints

Count Valid

Increment counter when all conditions are satisfied

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

int solution(int* arr, int arrSize, int a, int b, int c) {
    int count = 0;
    
    for (int i = 0; i < arrSize; i++) {
        for (int j = i + 1; j < arrSize; j++) {
            for (int k = j + 1; k < arrSize; k++) {
                if (abs(arr[i] - arr[j]) <= a &&
                    abs(arr[j] - arr[k]) <= b &&
                    abs(arr[i] - arr[k]) <= c) {
                    count++;
                }
            }
        }
    }
    
    return count;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array
    int arr[100];
    int arrSize = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        arr[arrSize++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    int a, b, c;
    scanf("%d", &a);
    scanf("%d", &b);
    scanf("%d", &c);
    
    int result = solution(arr, arrSize, a, b, c);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n³)

Three nested loops iterate through all possible triplets

⚠ Quadratic Growth

Space Complexity

O(1)

Only using constant extra variables

✓ Linear Space

23.2K Views

Medium Frequency

~15 min Avg. Time

892 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Triple Nested Loops — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler