Number of Arithmetic Triplets

easy array hash set two pointers

Problem

Given a strictly increasing array nums and an integer diff, count index triplets (i, j, k) with i < j < k such that nums[j] − nums[i] = diff and nums[k] − nums[j] = diff.

Inputnums = [0,1,4,6,7,10], diff = 3

Output2

(1,4,7) and (4,7,10) are arithmetic triplets.

nums

diff

def arithmetic_triplets(nums, diff):
    seen = set(nums)
    count = 0
    for x in nums:
        if x + diff in seen and x + 2 * diff in seen:
            count += 1
    return count

function arithmeticTriplets(nums, diff) {
  const seen = new Set(nums);
  let count = 0;
  for (const x of nums) {
    if (seen.has(x + diff) && seen.has(x + 2 * diff)) count++;
  }
  return count;
}

class Solution {
    public int arithmeticTriplets(int[] nums, int diff) {
        Set<Integer> seen = new HashSet<>();
        for (int x : nums) seen.add(x);
        int count = 0;
        for (int x : nums)
            if (seen.contains(x + diff) && seen.contains(x + 2 * diff)) count++;
        return count;
    }
}

int arithmeticTriplets(vector<int>& nums, int diff) {
    unordered_set<int> seen(nums.begin(), nums.end());
    int count = 0;
    for (int x : nums)
        if (seen.count(x + diff) && seen.count(x + 2 * diff)) count++;
    return count;
}

Explanation

An arithmetic triplet is three values that step up by exactly diff each time: x, x + diff, and x + 2*diff. Because the array is strictly increasing, the values are distinct, so a triplet of values corresponds to exactly one triplet of indices.

That observation lets us forget about indices entirely. We first drop every value into a hash set for O(1) membership checks.

Then we treat each value x as the smallest member of a potential triplet. If both x + diff and x + 2*diff are present in the set, we found one triplet and increment the counter.

Each value is checked once and each lookup is constant time, so the whole scan is linear. The set build is also linear, giving overall O(n) time.

Example: nums = [0,1,4,6,7,10], diff = 3. For x = 1 we find 4 and 7 → triplet. For x = 4 we find 7 and 10 → triplet. No other value anchors one, so the answer is 2.

Time: O(n) Space: O(n)