Count Good Triplets

Count Good Triplets

What is this problem about?

The "Count Good Triplets" coding problem asks you to find the number of "good" triplets in an integer array. A triplet $(arr[i], arr[j], arr[k])$ is defined as "good" if it satisfies three conditions: the indices must be in increasing order ($i < j < k$), and the absolute differences between the elements must be within specified bounds. Specifically, $|arr[i] - arr[j]| \le a$, $|arr[j] - arr[k]| \le b$, and $|arr[i] - arr[k]| \le c$.

Why is this asked in interviews?

This problem is frequently used by companies like Microsoft and Amazon to evaluate a candidate's understanding of nested loops and constraint checking. While it is an "Easy" difficulty problem, it tests your ability to write clean code that efficiently navigates array indices. It also serves as a baseline to see if a candidate can correctly implement a brute-force approach before moving on to more complex optimization tasks.

Algorithmic pattern used

The primary algorithmic pattern used here is Enumeration or Brute Force. Since the goal is to count all valid combinations of three indices, a triple-nested loop is the most straightforward way to explore the search space. Because the constraints on array length in such problems are typically small (often around 100), an $O(n^3)$ solution is perfectly acceptable.

Example explanation

Suppose we have an array arr = [4, 1, 2, 3] with limits a = 3, b = 2, c = 4.

1. We check indices $(0, 1, 2)$: values are $(4, 1, 2)$.
   • $|4 - 1| = 3 \le a$ (True)
   • $|1 - 2| = 1 \le b$ (True)
   • $|4 - 2| = 2 \le c$ (True)
   • This is a "good" triplet.
2. We check indices $(0, 1, 3)$: values are $(4, 1, 3)$.
   • $|4 - 1| = 3 \le a$ (True)
   • $|1 - 3| = 2 \le b$ (True)
   • $|4 - 3| = 1 \le c$ (True)
   • This is also a "good" triplet. If we continued this for all $(i, j, k)$, we would find the total count.

Common mistakes candidates make

One common mistake is using incorrect index ranges in the nested loops, leading to IndexOutOfBounds errors or missing certain triplets. Another error is neglecting one of the three conditions (often the $|arr[i] - arr[k]| \le c$ check). Candidates sometimes also try to over-optimize the problem using sorting, which is incorrect because the relative order of elements (the $i < j < k$ condition) must be preserved.

Interview preparation tip

When solving enumeration problems, focus on readability. Use descriptive variable names for your limits ($a, b, c$) and clearly define your loop boundaries. Even for simple problems, explaining the time complexity ($O(n^3)$) and why it's sufficient for the given constraints shows maturity as an engineer.