Number of Arithmetic Triplets

Number of Arithmetic Triplets

What is this problem about?

The Number of Arithmetic Triplets problem asks you to count the number of triplets (i, j, k) where i < j < k such that arr[j] - arr[i] == arr[k] - arr[j] == diff (given constant difference). The array is guaranteed to be sorted and distinct. This easy coding problem has both O(n²) and O(n) solutions.

Why is this asked in interviews?

Meta and Google ask this as a quick assessment of hash set / two-pointer thinking on sorted arrays. The O(n) solution using a hash set to check for the two required neighbors is the expected answer. The array, hash table, two pointers, and enumeration interview pattern is demonstrated.

Algorithmic pattern used

Hash set for O(n) lookup. Build a set of all array values. For each element v, check if v - diff and v - 2*diff are also in the set. If both exist, it's a valid triplet. Count all such v values.

Alternatively, two pointers: for each middle element j, use two pointers for i and k. But the hash set approach is simpler.

Example explanation

Array: [0, 1, 4, 6, 7, 10], diff=3.

• v=4: 4-3=1 ✓, 4-6=-2 ✗ → not a triplet. Wait: need v+diff too. Let me re-read: triplet needs arr[j]-arr[i]=diff AND arr[k]-arr[j]=diff. So for middle v: check v-diff and v+diff both in set.
• v=1: v-diff=1-3=-2 ✗.
• v=4: v-diff=1 ✓, v+diff=7 ✓. Triplet (1,4,7).
• v=7: v-diff=4 ✓, v+diff=10 ✓. Triplet (4,7,10). Count = 2.

Common mistakes candidates make

• Checking only v + diff without verifying v - diff also exists.
• Using triple nested loops O(n³) when O(n) is straightforward.
• Confusing the hash set approach for finding all three elements vs just the middle.
• Not building the set from the full array first before querying.

Interview preparation tip

Arithmetic triplet problems reduce to "given middle element, can I find left and right?" A hash set makes this O(1) per element. Build the set first, then check each element as a potential middle. This approach extends to arithmetic sequences of any length: for k-length sequences, check k-1 progressions from any starting element. Practice similar "count sequences satisfying arithmetic property" problems to develop fast hash-set-based thinking.