Number of Arithmetic Triplets

Easy
273.

Number of Arithmetic Triplets

Number of Arithmetic Triplets is an easy coding problem on arrays, hash table and two pointers, asked in Amazon and Google interviews.

You are given a strictly increasing integer array nums and a positive integer diff.

Count the triples (i, j, k) with i < j < k such that nums[j] - nums[i] == diff and nums[k] - nums[j] == diff.

Example 1

Input
nums = [0,1,4,6,7,10], diff = 3
Output
2
Explanation
The triples are (1,2,4) giving 1,4,7 and (2,4,5) giving 4,7,10.

Example 2

Input
nums = [4,5,6,7,8,9], diff = 2
Output
2

Example 3

Input
nums = [1,2,3], diff = 5
Output
0

Constraints

  • 3 <= nums.length <= 40
  • 0 <= nums[i] <= 200
  • nums is strictly increasing.
  • 1 <= diff <= 50
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @param {number} diff
 * @return {number}
 */
var arithmeticTriplets = function(nums, diff) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Number of Arithmetic Triplets — Problem & Solution

Number of Arithmetic Triplets solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.

Number of Arithmetic Triplets is an easy coding problem on arrays, hash table and two pointers, asked in Amazon and Google interviews.

Problem statement

You are given a strictly increasing integer array nums and a positive integer diff.

Count the triples (i, j, k) with i < j < k such that nums[j] - nums[i] == diff and nums[k] - nums[j] == diff.

Example 1

Input: nums = [0,1,4,6,7,10], diff = 3
Output: 2
Explanation: The triples are (1,2,4) giving 1,4,7 and (2,4,5) giving 4,7,10.

Example 2

Input: nums = [4,5,6,7,8,9], diff = 2
Output: 2

Example 3

Input: nums = [1,2,3], diff = 5
Output: 0

Constraints

  • 3 <= nums.length <= 40
  • 0 <= nums[i] <= 200
  • nums is strictly increasing.
  • 1 <= diff <= 50

Hints for Number of Arithmetic Triplets

  1. Hint 1

    The array is strictly increasing, so a value determines its position — index order comes for free.

  2. Hint 2

    Put every value in a hash set, then for each x check whether x + diff and x + 2·diff are present.

  3. Hint 3

    That counts each triple once, keyed by its smallest element.

How to solve Number of Arithmetic Triplets

Strictly increasing means a value determines its index, so put every value in a set and count x with both x + diff and x + 2·diff present.

Approach

  1. Build a set of the values.
  2. Count elements x where x + diff and x + 2*diff are in the set.

Why it works

Each arithmetic triple is uniquely identified by its smallest element, and strict monotonicity guarantees the three values appear in index order.

Complexity

  • Time — O(n)
  • Space — O(n)

Pitfalls

  • Without strict increase, duplicate values would need multiplicity handling.

Reference solution

Python

def arithmeticTriplets(nums, diff: int) -> int:
    present = set(nums)
    return sum(1 for x in nums if x + diff in present and x + 2 * diff in present)

Java

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

C++

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

JavaScript

var arithmeticTriplets = function(nums, diff) {
    const present = new Set(nums);
    let count = 0;
    for (let i = 0; i < nums.length; i++) {
        if (present.has(nums[i] + diff) && present.has(nums[i] + 2 * diff)) count++;
    }
    return count;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets