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.
- Difficulty: Easy
- Topics: Arrays, Hash Table, Two Pointers, Enumeration
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
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 <= 400 <= nums[i] <= 200nums is strictly increasing.1 <= diff <= 50
Hints for Number of Arithmetic Triplets
Hint 1
The array is strictly increasing, so a value determines its position — index order comes for free.
Hint 2
Put every value in a hash set, then for each
xcheck whetherx + diffandx + 2·diffare present.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
- Build a set of the values.
- Count elements
xwherex + diffandx + 2*diffare 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