Leetcode 1534. Count Good Triplets
Count the number of index triplets (i < j < k) in arr such that the pairwise absolute differences satisfy |arr[i]-arr[j]| ≤ a, |arr[j]-arr[k]| ≤ b, and |arr[i]-arr[k]| ≤ c. With arr.length ≤ 100, the constraints make a direct check over all triplets efficient.
Asked at:
DESCRIPTION
Count the number of index triplets (i < j < k) in arr such that the pairwise absolute differences satisfy |arr[i]-arr[j]| ≤ a, |arr[j]-arr[k]| ≤ b, and |arr[i]-arr[k]| ≤ c. With arr.length ≤ 100, the constraints make a direct check over all triplets efficient.
Input:
arr = [1, 5, 3, 4, 2], a = 2, b = 3, c = 4
Output:
4
Explanation: Valid triplets are (0,2,4): |1-3|=2≤2, |3-2|=1≤3, |1-2|=1≤4; (0,3,4): |1-4|=3>2 ✗;
(1,2,4): |5-3|=2≤2, |3-2|=1≤3, |5-2|=3≤4 ✓;
and (2,3,4): |3-4|=1≤2, |4-2|=2≤3, |3-2|=1≤4 ✓
Constraints:
- 3 <= arr.length <= 100
- 1 <= arr[i] <= 1000
- 0 <= a, b, c <= 1000
- All triplets must satisfy i < j < k (strict ordering)
Understanding the Problem
Let's understand what we're being asked to do. We have an array like [1, 5, 3, 4, 2] and three threshold values a=2, b=3, c=4. We need to count how many triplets (i, j, k) where i < j < k satisfy ALL three conditions simultaneously.
Let's trace through one example triplet: indices (0, 2, 4) correspond to values (1, 3, 2). Check the conditions:
- |arr[0] - arr[2]| = |1 - 3| = 2 ≤ a=2 ✓
- |arr[2] - arr[4]| = |3 - 2| = 1 ≤ b=3 ✓
- |arr[0] - arr[4]| = |1 - 2| = 1 ≤ c=4 ✓
All three conditions are satisfied, so this triplet counts!
Important constraint: The array length is at most 100, which means there are at most 100 * 99 * 98 / 6 ≈ 161,700 possible triplets. This small size makes checking every triplet feasible.
Edge cases to consider: What if the array has fewer than 3 elements? (return 0). What if all values are the same? What if a, b, or c are 0 (very strict)?
Building Intuition
With only 100 elements maximum, we can afford to check every possible triplet (i, j, k) where i < j < k. For each triplet, we compute three absolute differences and verify all three conditions.
The key insight is recognizing that the small input size makes the brute force approach practical - we don't need a clever optimization here.
Sometimes the most straightforward solution IS the right solution! With n ≤ 100, even an O(n³) algorithm runs in under a millisecond on modern hardware.
This is an important lesson: premature optimization can waste time. Always consider the constraints before reaching for complex algorithms.
Think about how you'd solve this by hand with a small array like [1, 3, 5]:
You'd naturally check the only triplet (0, 1, 2): compute |1-3|, |3-5|, and |1-5|, then verify against a, b, c.
With 100 elements, you'd do the same process systematically - three nested loops to generate all triplets, then three comparisons per triplet. The constraint-driven approach tells us this is perfectly acceptable.
Common Mistakes
Optimal Solution
Use three nested loops to generate all possible triplets (i, j, k) where i < j < k. For each triplet, compute the three absolute differences: |arr[i] - arr[j]|, |arr[j] - arr[k]|, and |arr[i] - arr[k]|. Check if all three differences satisfy their respective thresholds a, b, and c. If all conditions are met, increment the count. This direct enumeration approach is optimal given the small constraint of n ≤ 100.
Start counting good triplets
0 / 79
Test Your Knowledge
Login to take the complexity quiz and track your progress
Complexity Analysis
Time Complexity: O(n³) Three nested loops iterate through all possible triplets, giving cubic time complexity. With n ≤ 100, this means at most ~161,700 triplets to check, which is very fast
Space Complexity: O(1) We only use a constant amount of extra space for loop counters and the count variable, regardless of input size
What We've Learned
- Brute force viability with constraint analysis: When array size is small (n ≤ 100), a O(n³) triple nested loop is perfectly acceptable - always check constraints before optimizing, as 100³ = 1,000,000 operations run in milliseconds and simpler code reduces bug risk.
- Sequential condition checking optimization: Evaluate conditions in order of computational cost - check |arr[i]-arr[j]| ≤ a first, then |arr[j]-arr[k]| ≤ b, and finally |arr[i]-arr[k]| ≤ c to short-circuit and skip unnecessary comparisons when early conditions fail.
- Index ordering enforcement: Use i < j < k loop structure (outer loop i: 0→n-3, middle loop j: i+1→n-2, inner loop k: j+1→n-1) to naturally guarantee the ordering constraint without additional checks - the loop bounds themselves enforce the triplet relationship.
- Absolute difference pattern: Problems involving pairwise comparisons with threshold constraints often require checking all combinations when no mathematical relationship exists between the constraints - recognize when conditions are independent and cannot be simplified algebraically.
- Space-time tradeoff awareness: This problem demonstrates choosing O(1) space with O(n³) time over complex optimizations - for small inputs, the simplicity of direct enumeration outweighs sophisticated data structures like coordinate compression or range trees that add implementation complexity.
- Combinatorial counting template: When counting valid tuples with multiple constraints, the pattern is: iterate all combinations, apply filters sequentially, increment counter - this enumerate-and-filter approach applies to many counting problems where constraints don't allow mathematical closed-form solutions.
Related Concepts and Problems to Practice
medium
This problem involves finding triplets in an array that satisfy certain conditions, similar to Count Good Triplets. While 3-Sum uses two pointers for optimization, it teaches the fundamental pattern of iterating through triplets and checking conditions, which is directly applicable to understanding triplet enumeration problems.
medium
This problem counts valid triplets (i, j, k) where array elements satisfy triangle inequality conditions, which is conceptually very similar to Count Good Triplets where triplets must satisfy multiple pairwise difference constraints. Both problems involve checking relationships between three elements and counting valid combinations.
medium
While Count Good Triplets uses nested loops, understanding how to systematically generate and evaluate combinations of elements (like in Subsets) provides insight into exhaustive enumeration patterns. This helps build intuition for problems that require checking all possible combinations of array elements.
Test Your Understanding
Why is array the right data structure for this problem?
array provides the optimal access pattern
It's the only data structure that works
It's the easiest to implement
It uses the least memory
Select an answer to see the explanation
Question Timeline
See when this question was last asked and where, including any notes left by other candidates.
Late December, 2024
Mid-level
Count Valid Triples with Absolute Difference Constraints
Early September, 2024
Mid-level
Find triplets i,j,k in a string s where s[i..j] and s[j+1..k] have the same count of distinct characters
Early September, 2024
Mid-level
Given a stream of numbers and a DISTANCE value, find triplets (a, b, c) where the absolute difference between any pair is less than or equal to DISTANCE. Remove found triplets from the stream.
Comments
Hello Interview Premium
Your account is free and you can post anonymously if you choose.