Count Good Triplets solution and explanation
Google
9 more videos on this problem
Count Good Triplets - Leetcode 1534 - PythonNeetCodeIO · 22:48 · 11K views
Count Good Triplets | Simple Approach | Slight Improvements | Leetcode 1534 | codestorywithMIKcodestorywithMIK · 10:20 · 7K views
leetcode - 1534 Count Good Triplets Solution & ExplanationlitCode · 6:59 · 2K views
1534. Count Good Triplets (Leetcode Easy)Programming Live with Larry · 2:01 · 1K views
LeetCode 1534 Count Good Triplets | Easy | Medium Follow up with Prefix Sum Range QueryCode Harmony · 25:28 · 1K views
LeetCode 1534. Count Good Triplets Solution Explained - JavaAlgorithms and Data Structures Course · 8:02 · 715 views
Leetcode 1534. Count Good Triplets | Brute Force & Optimized Prefix Sum SolutionsStatLearn Tech · 16:41 · 547 views
Count Good Triplets | Leetcode 1534Competitive Coding · 2:57 · 517 views
Count Good Triplets | LeetCode 1534 | Java Code | Developer CoderDeveloper Coder · 5:21 · 321 views
How to Solve "1534 Count Good Triplets" on LeetCode? - JavascriptBecoming A Better Dev (with David) · 7:16 · 258 views
The problem
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 <= 1000 <= arr[i] <= 10000 <= 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.
def count_good_triplets(arr, a, b, c):
count = 0
n = len(arr)
for i in range(n - 2):
for j in range(i + 1, n - 1):
for k in range(j + 1, n):
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
arr = [3, 0, 1, 1, 9, 7]
a, b, c = 7, 2, 3
print("Number of good triplets:", count_good_triplets(arr, a, b, c))public class GoodTriplets {
public static int countGoodTriplets(int[] arr, int a, int b, int c) {
int count = 0;
int n = arr.length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; 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;
}
public static void main(String[] args) {
int[] arr = {3, 0, 1, 1, 9, 7};
int a = 7, b = 2, c = 3;
System.out.println("Number of good triplets: " + countGoodTriplets(arr, a, b, c));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
int count = 0;
int n = arr.size();
for (int i = 0; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
for (int k = j + 1; k < n; ++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() {
vector<int> arr = {3, 0, 1, 1, 9, 7};
int a = 7, b = 2, c = 3;
cout << "Number of good triplets: " << countGoodTriplets(arr, a, b, c) << endl;
return 0;
}function countGoodTriplets(arr, a, b, c) {
let count = 0;
const n = arr.length;
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; j++) {
for (let k = j + 1; k < n; 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;
}
const arr = [3, 0, 1, 1, 9, 7];
const a = 7, b = 2, c = 3;
console.log("Number of good triplets: " + countGoodTriplets(arr, a, b, c));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int countGoodTriplets(int* arr, int arrSize, int a, int b, int c) {
int count = 0;
for (int i = 0; i < arrSize - 2; i++) {
for (int j = i + 1; j < arrSize - 1; 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() {
int arr[] = {3, 0, 1, 1, 9, 7};
int a = 7, b = 2, c = 3;
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("Number of good triplets: %d\n", countGoodTriplets(arr, arrSize, a, b, c));
return 0;
}using System;
class GoodTriplets {
public static int CountGoodTriplets(int[] arr, int a, int b, int c) {
int count = 0;
int n = arr.Length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; j++) {
for (int k = j + 1; k < n; 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;
}
static void Main() {
int[] arr = {3, 0, 1, 1, 9, 7};
int a = 7, b = 2, c = 3;
Console.WriteLine("Number of good triplets: " + CountGoodTriplets(arr, a, b, c));
}
}This Python implementation uses three nested loops to explore every combination of three indices and filters them based on the provided conditions of good triplets.
Time Complexity: O(n^3). Space Complexity: O(1).
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.
def count_good_triplets(arr, a, b, c):
count = 0
n = len(arr)
for i in range(n - 2):
for j in range(i + 1, n - 1):
if abs(arr[i] - arr[j]) > a:
continue
for k in range(j + 1, n):
if abs(arr[j] - arr[k]) > b:
continue
if abs(arr[i] - arr[k]) <= c:
count += 1
return count
arr = [3, 0, 1, 1, 9, 7]
a, b, c = 7, 2, 3
print("Number of good triplets:", count_good_triplets(arr, a, b, c))public class GoodTriplets {
public static int countGoodTriplets(int[] arr, int a, int b, int c) {
int count = 0;
int n = arr.length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; 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) continue;
if (Math.abs(arr[i] - arr[k]) <= c) {
count++;
}
}
}
}
return count;
}
public static void main(String[] args) {
int[] arr = {3, 0, 1, 1, 9, 7};
int a = 7, b = 2, c = 3;
System.out.println("Number of good triplets: " + countGoodTriplets(arr, a, b, c));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
int count = 0;
int n = arr.size();
for (int i = 0; i < n - 2; ++i) {
for (int j = i + 1; j < n - 1; ++j) {
if (abs(arr[i] - arr[j]) > a) continue;
for (int k = j + 1; k < n; ++k) {
if (abs(arr[j] - arr[k]) > b) continue;
if (abs(arr[i] - arr[k]) <= c) {
++count;
}
}
}
}
return count;
}
int main() {
vector<int> arr = {3, 0, 1, 1, 9, 7};
int a = 7, b = 2, c = 3;
cout << "Number of good triplets: " << countGoodTriplets(arr, a, b, c) << endl;
return 0;
}function countGoodTriplets(arr, a, b, c) {
let count = 0;
const n = arr.length;
for (let i = 0; i < n - 2; i++) {
for (let j = i + 1; j < n - 1; 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) continue;
if (Math.abs(arr[i] - arr[k]) <= c) {
count++;
}
}
}
}
return count;
}
const arr = [3, 0, 1, 1, 9, 7];
const a = 7, b = 2, c = 3;
console.log("Number of good triplets: " + countGoodTriplets(arr, a, b, c));#include <stdio.h>
#include <stdlib.h>
#include <math.h>
int countGoodTriplets(int* arr, int arrSize, int a, int b, int c) {
int count = 0;
for (int i = 0; i < arrSize - 2; i++) {
for (int j = i + 1; j < arrSize - 1; j++) {
if (abs(arr[i] - arr[j]) > a) continue;
for (int k = j + 1; k < arrSize; k++) {
if (abs(arr[j] - arr[k]) > b) continue;
if (abs(arr[i] - arr[k]) <= c) {
count++;
}
}
}
}
return count;
}
int main() {
int arr[] = {3, 0, 1, 1, 9, 7};
int a = 7, b = 2, c = 3;
int arrSize = sizeof(arr) / sizeof(arr[0]);
printf("Number of good triplets: %d\n", countGoodTriplets(arr, arrSize, a, b, c));
return 0;
}using System;
class GoodTriplets {
public static int CountGoodTriplets(int[] arr, int a, int b, int c) {
int count = 0;
int n = arr.Length;
for (int i = 0; i < n - 2; i++) {
for (int j = i + 1; j < n - 1; 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) continue;
if (Math.Abs(arr[i] - arr[k]) <= c) {
count++;
}
}
}
}
return count;
}
static void Main() {
int[] arr = {3, 0, 1, 1, 9, 7};
int a = 7, b = 2, c = 3;
Console.WriteLine("Number of good triplets: " + CountGoodTriplets(arr, a, b, c));
}
}In this Python script, early exits with `continue` help skip if the criteria are compromised at any loop level, slightly improving efficiency.
Time Complexity: O(n^3) but with optimistic practical performance due to early termination of iterations. Space Complexity: O(1).
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).
function countGoodTriplets(arr: number[], a: number, b: number, c: number): number {
let n = arr.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
for (let k = j + 1; k < n; ++k) {
if (
Math.abs(arr[i] - arr[j]) <= a &&
Math.abs(arr[j] - arr[k]) <= b &&
Math.abs(arr[i] - arr[k]) <= c
) {
++ans;
}
}
}
}
return ans;
}func countGoodTriplets(arr []int, a int, b int, c int) (ans int) {
n := len(arr)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
if abs(arr[i]-arr[j]) <= a && abs(arr[j]-arr[k]) <= b && abs(arr[i]-arr[k]) <= c {
ans++
}
}
}
}
return
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}impl Solution {
pub fn count_good_triplets(arr: Vec<i32>, a: i32, b: i32, c: i32) -> i32 {
let n = arr.len();
let mut ans = 0;
for i in 0..n {
for j in i + 1..n {
for k in j + 1..n {
if (arr[i] - arr[j]).abs() <= a && (arr[j] - arr[k]).abs() <= b && (arr[i] - arr[k]).abs() <= c {
ans += 1;
}
}
}
}
ans
}
}Complexity comparison
| Approach | Complexity |
|---|---|
| Brute Force Approach | Time Complexity: O(n^3). Space Complexity: O(1). |
| Optimized Combination with Early Break | Time Complexity: O(n^3) but with optimistic practical performance due to early termination of iterations. Space Complexity: O(1). |
| Enumeration | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Baseline solution when constraints are small and clarity is preferred |
| Enumeration with Early Pruning | O(n^3) worst case | O(1) | General case; reduces unnecessary checks by filtering invalid (i, j) pairs early |
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.