Algorithms. The “Count Good Triplets” problem

Original statement: 1534. Count Good Triplets

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

Three‑loop solution

function countGoodTripletsNaive(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 &&
          Math.abs(arr[i] - arr[k]) <= c
        ) {
          count++;
        }
      }
    }
  }
  return count;
}

My approach is straightforward: we iterate for each element of the triplet and check the required conditions.

Time complexity: O(n³); space: O(1).

Because the constraint 0 ≤ i < j < k < arr.length means the indices in a triplet must be in ascending order, the loop for the first element must guarantee that two more elements remain. Therefore, it runs only up to array length – 3, i.e. n – 3:

for (let i = 0; i < n - 2; i++

Nxt we start the loop for the second triplet element j. By the same logic we must still have at least one element left for k, so we limit the loop to n – 2:

for (let j = i + 1; j < n - 1; j++)

Now we can check the first condition to decide whether it makes sense to proceed to the loop over the third element:

if (Math.abs(arr[i] - arr[j]) > a) continue;

If the absolute difference exceeds a, we simply continue with the next j.

For the third element we no longer need to reserve room after it, so the loop goes to the end of the array:

for (let k = j + 1; k < n; k++)

Inside we test the remaining conditions Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c and, if both hold, increment count: count++;

Brief walkthrough

For arr = [3, 0, 1, 1, 9, 7], a = 7, b = 2, c = 3:

1. i = 0 (arr[i] = 3)
   • j = 1 (arr[j] = 0): |3 – 0| = 3 ≤ 7 ⇒ proceed to k
     • k = 2 (1): |0 – 1| = 1 ≤ 2, |3 – 1| = 2 ≤ 3 ⇒ found (3, 0, 1)
     • k = 3 (1): same ⇒ found
     • k = 4, 5: either b or c fails ⇒ skip
   • j = 2, 3 (arr[j] = 1): |3 – 1| = 2 ≤ 7 ⇒ continue with k…
   • …and so on for all j, k.
2. i = 1 (arr[i] = 0), i = 2, i = 3 — analogous checks.

End result: 4 triplets.