Practice/Google/Leetcode 1534. Count Good Triplets

Leetcode 1534. Count Good Triplets

CodingMust

Problem

You are given an array of integers arr and three non-negative integers a, b, and c.

Your task is to count how many triplets of indices (i, j, k) exist such that:

• The indices are in strictly increasing order: i < j < k
• The absolute difference between arr[i] and arr[j] is at most a
• The absolute difference between arr[j] and arr[k] is at most b
• The absolute difference between arr[i] and arr[k] is at most c

Return the total count of such valid triplets.

Requirements

1. Count all index triplets where i < j < k
2. Each triplet must satisfy all three distance constraints simultaneously
3. Return the total count as an integer
4. Handle arrays with at least 3 elements

Constraints

• 3 ≤ arr.length ≤ 100
• 0 ≤ arr[i] ≤ 1000
• 0 ≤ a, b, c ≤ 1000
• Time complexity: O(n³) is acceptable given the small array size
• Space complexity: O(1) auxiliary space

Examples

Example 1:

` Input: arr = [3, 0, 1, 1, 9, 7], a = 7, b = 2, c = 3 Output: 4 Explanation: The valid triplets are:

• (0, 2, 3): |3-1| = 2 ≤ 7, |1-1| = 0 ≤ 2, |3-1| = 2 ≤ 3
• (0, 3, 4): |3-1| = 2 ≤ 7, |1-9| = 8 > 2 (invalid) Wait, let me recalculate. After checking all combinations, 4 triplets satisfy all conditions. `

Example 2:

Input: arr = [1, 1, 2, 2, 3], a = 5, b = 5, c = 5 Output: 10 Explanation: With generous thresholds, all C(5,3) = 10 triplets are valid since the array values are close together.

Example 3:

Input: arr = [1, 5, 10, 15, 20], a = 1, b = 1, c = 1 Output: 0 Explanation: All consecutive differences exceed 1, so no triplet can satisfy all three constraints.