Number of Arithmetic Triplets - Video Solutions

Problem Overview: You receive a strictly increasing integer array nums and a value diff. The goal is to count triplets (i, j, k) where i < j < k, nums[j] - nums[i] = diff, and nums[k] - nums[j] = diff. In other words, you are looking for three numbers that form an arithmetic progression with a fixed difference.

Approach 1: Iterative Hash Set Enumeration (O(n) time, O(n) space)

Because the array is strictly increasing, each value can be treated as the potential start of an arithmetic sequence. Insert all elements into a hash set for constant‑time membership checks. Then iterate through each number x in nums and check whether x + diff and x + 2 * diff both exist in the set. If they do, the triplet (x, x + diff, x + 2 * diff) forms a valid arithmetic progression. This works because the sorted property guarantees index order automatically when the values exist. The algorithm performs one pass through the array and two constant-time lookups per element, giving O(n) time and O(n) space. This is the cleanest and most common solution using a hash table with simple enumeration.

Approach 2: Recursive Enumeration (O(n) time, O(n) space)

A recursive version follows the same idea but processes elements through recursive calls instead of a loop. Maintain a set containing all numbers and recursively evaluate each index as the potential start of a triplet. At each step, check whether nums[i] + diff and nums[i] + 2 * diff exist in the set and add to the count if they do. The recursion advances to the next index until the array is exhausted. While recursion does not improve asymptotic performance, it demonstrates how the enumeration logic can be expressed functionally. Time complexity remains O(n) since each element is evaluated once, and space complexity is O(n) due to the set plus recursion stack.

Recommended for interviews: The iterative hash set solution is what most interviewers expect. It shows you recognize the arithmetic pattern and reduce the problem to constant-time membership checks instead of nested loops. A brute-force triple loop would take O(n^3) and is unnecessary given the sorted array property. Demonstrating the optimized set-based enumeration highlights familiarity with array traversal patterns and efficient lookup strategies.