Skip to main content
Talentd

Count Good Triplets - Solution & Explanation

EasyArrayEnumeration17 min readAsked at: Amazon, Meta, Google +2
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You get an integer array and three thresholds a, b, and c. Count triplets of indices (i, j, k) such that i < j < k and three constraints hold: |arr[i] - arr[j]| ≤ a, |arr[j] - arr[k]| ≤ b, and |arr[i] - arr[k]| ≤ c. The task is purely about enumerating valid index combinations while efficiently filtering out invalid ones.

Approach 1: Brute Force Enumeration (O(n³) time, O(1) space)

The most direct solution checks every possible triplet. Use three nested loops where i runs from 0..n-3, j from i+1..n-2, and k from j+1..n-1. For each combination, compute the three absolute differences and verify they satisfy the constraints. If all conditions hold, increment the result counter. This approach relies only on simple iteration over the array and constant-time arithmetic checks.

Although the time complexity is O(n³), the constraints of the problem keep n small enough that a full enumeration is practical. The implementation is straightforward and often the first version written during interviews to confirm understanding of the conditions.

Approach 2: Optimized Enumeration with Early Pruning (O(n³) worst-case time, O(1) space)

This version keeps the same triple-loop structure but avoids unnecessary work by validating constraints as early as possible. After choosing indices i and j, immediately check |arr[i] - arr[j]| ≤ a. If this fails, skip the entire inner k loop because no triplet starting with that pair can be valid. Only when the first condition passes do you iterate k and test the remaining two constraints.

Inside the k loop, compute |arr[j] - arr[k]| and |arr[i] - arr[k]| and increment the count when both satisfy their limits. This pruning strategy significantly reduces the number of checks in practice, especially when many pairs already violate the first constraint. The technique is a common pattern in enumeration problems: validate cheaper conditions early to shrink the search space.

Recommended for interviews: Start with the brute force explanation because it clearly matches the problem definition and demonstrates correct reasoning about index ordering. Then show the optimized enumeration where the first constraint filters pairs before exploring the third index. Interviewers expect the pruning step since it reduces unnecessary iterations while keeping the implementation simple and readable.

Approach 1: Brute Force Approach

The brute force approach involves using three nested loops, iterating over all possible combinations of indices (i, j, k) with the condition i < j < k. For each triplet, we check if the given conditions |arr[i] - arr[j]| <= a, |arr[j] - arr[k]| <= b, and |arr[i] - arr[k]| <= c hold true. If they do, we increment the count of good triplets.

This C solution follows a straightforward brute force approach using three nested loops. It iterates over all the indices i, j, and k such that 0 <= i < j < k < arr.size. For each such combination, it checks if all given conditions are satisfied.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n^3), where n is the array's length due to three nested loops. Space Complexity: O(1), only basic variables are used.

Try this approach in the editor →

Approach 2: Optimized Combination with Early Break

This approach also uses three nested loops, but incorporates early stopping by breaking out of the inner loops if the conditions become unsatisfiable. This reduces unnecessary iterations and slightly optimizes the solution in practical scenarios.

This C solution enhances the brute force logic with early exits from loops if the condition of a particular segment fails (e.g., exits j-loop if |arr[i] - arr[j]| > a).

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: Still O(n^3) in the worst case but can be faster in practice due to early breaks. Space Complexity: O(1).

Try this approach in the editor →

Approach 3: Enumeration

We can enumerate all i, j, and k where i \lt j \lt k, and check if they simultaneously satisfy |arr[i] - arr[j]| \le a, |arr[j] - arr[k]| \le b, and |arr[i] - arr[k]| \le c. If they do, we increment the answer by one.

After enumerating all possible triplets, we get the answer.

The time complexity is O(n^3), where n is the length of the array arr. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustC#

Python

Java

C++

Go

TypeScript

Rust

C#

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(n^3), where n is the array's length due to three nested loops. Space Complexity: O(1), only basic variables are used.

Optimized Combination with Early Break

Time Complexity: Still O(n^3) in the worst case but can be faster in practice due to early breaks. Space Complexity: O(1).

Enumeration—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(n^3)O(1)Baseline solution when constraints are small and clarity is preferred
Enumeration with Early PruningO(n^3) worst caseO(1)General case; reduces unnecessary checks by filtering invalid (i, j) pairs early

Video Solution

Count Good Triplets - Leetcode 1534 - Python • NeetCodeIO • 11,704 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Count Good Triplets easy or hard?
Count Good Triplets is classified as an Easy problem on LeetCode. The logic mainly involves careful enumeration of index combinations and verifying simple conditions, making it a good practice problem for array traversal and constraint checking.
How to solve Count Good Triplets in O(n)?
An O(n) solution is generally not feasible because the problem requires checking relationships among three different indices. Without additional constraints like sorted order or restricted values, every valid triplet must be considered indirectly. With n ≤ 100 in the problem constraints, the O(n^3) enumeration approach is efficient enough.
What is the best approach for Count Good Triplets?
The practical approach is enumeration with early pruning. Iterate over all index triplets (i < j < k) but validate |arr[i] - arr[j]| ≤ a before entering the third loop. This keeps the algorithm simple while skipping many invalid combinations. The worst-case time complexity remains O(n^3) with O(1) extra space.
What data structure is used in Count Good Triplets?
The problem primarily uses a simple array and nested iteration. No advanced data structures are required because the constraints can be verified with direct index access and arithmetic comparisons.
What is the time complexity of Count Good Triplets?
The standard solution runs in O(n^3) time because it checks combinations of three indices from the array. Each triplet requires constant-time comparisons for the three absolute difference conditions. Space complexity is O(1) since only a counter and loop variables are used.
Count Good Triplets Python or Java solution approach?
Both Python and Java implementations follow the same pattern: three nested loops enforcing i < j < k and checking the three absolute difference constraints. The optimized version adds an early check for |arr[i] - arr[j]| ≤ a before running the inner loop to reduce unnecessary work.
Is Count Good Triplets asked at Google, Amazon, or Meta?
Count Good Triplets is categorized as an easy array enumeration problem and is more common in practice platforms and entry-level interview rounds. Variations of triplet counting with constraints appear in interviews at companies like Amazon and Google, often with stricter optimization requirements.

Ready to solve this problem?

Practice Count Good Triplets with our built-in code editor and test cases.

Practice on FleetCode
Previous

Count Special Quadruplets

Next

Number of Unequal Triplets in Array