Number of Arithmetic Triplets solution and explanation
Google
9 more videos on this problem
Leetcode 2367. Number of Arithmetic Triplets | Weekly Contest 305. EasyCode with Alisha · 4:46 · 5K views
2367. Number of Arithmetic Triplets|| Leetcode Weekly Contest 305 || LeetCode 2367Bro Coders · 9:00 · 4K views
Leetcode 2367 | Number of Arithmetic Triplets (New)AverageLeeter · 16:49 · 2K views
2367. Number of Arithmetic Triplets (Leetcode Easy)Programming Live with Larry · 4:35 · 1K views
Number of Arithmetic Triplets Leetcode 2367 coding interview questionInterview Ready · 16:01 · 959 views
LeetCode 2367 | Number of Arithmetic Triplets | HashSet | JavaSleepy Cracker · 3:06 · 859 views
LeetCode 2367 : Number of Arithmetic Triplets | Solution in JAVAAmit Manjarly · 11:38 · 514 views
LeetCode 2367 : Number of Arithmetic Triplets | Solution in C++Amit Manjarly · 8:49 · 263 views
Number of Arithmetic Triplets | Leetcode 2367 | Approach + Code with explanation.Pirai's Academy · 16:01 · 212 views
2367. Number of Arithmetic Triplets || Leetcode weekly challenge || C++CS warriors · 3:31 · 199 views
The problem
You are given a 0-indexed, strictly increasing integer array nums and a positive integer diff. A triplet (i, j, k) is an arithmetic triplet if the following conditions are met:
i < j < k,nums[j] - nums[i] == diff, andnums[k] - nums[j] == diff.
Return the number of unique arithmetic triplets.
Example 1:
Input: nums = [0,1,4,6,7,10], diff = 3 Output: 2 Explanation: (1, 2, 4) is an arithmetic triplet because both 7 - 4 == 3 and 4 - 1 == 3. (2, 4, 5) is an arithmetic triplet because both 10 - 7 == 3 and 7 - 4 == 3.
Example 2:
Input: nums = [4,5,6,7,8,9], diff = 2 Output: 2 Explanation: (0, 2, 4) is an arithmetic triplet because both 8 - 6 == 2 and 6 - 4 == 2. (1, 3, 5) is an arithmetic triplet because both 9 - 7 == 2 and 7 - 5 == 2.
Constraints:
3 <= nums.length <= 2000 <= nums[i] <= 2001 <= diff <= 50numsis strictly increasing.
Approach overview
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.
Approach 1: Approach 1: Iterative Solution
This approach focuses on solving the problem iteratively, using a loop to process elements step by step. Choose this method if the problem is naturally sequential or requires processing each element in turn.
def iterative_solution(data):
for num in data:
print(num, end=' ') # Process each element
if __name__ == "__main__":
data = [1, 2, 3, 4, 5]
iterative_solution(data)import java.util.List;
public class IterativeSolution {
public static void iterativeSolution(List<Integer> data) {
for(int num : data) {
System.out.print(num + " "); // Process each element
}
}
public static void main(String[] args) {
List<Integer> data = List.of(1, 2, 3, 4, 5);
iterativeSolution(data);
}
}#include <iostream>
#include <vector>
void iterativeSolution(std::vector<int>& data) {
for(int num : data) {
std::cout << num << " "; // Process each element
}
}
int main() {
std::vector<int> data = {1, 2, 3, 4, 5};
iterativeSolution(data);
return 0;
}function iterativeSolution(data) {
data.forEach(num => console.log(num)); // Process each element
}
let data = [1, 2, 3, 4, 5];
iterativeSolution(data);#include <stdio.h>
void iterativeSolution(int data[], int size) {
for(int i = 0; i < size; i++) {
printf("%d ", data[i]); // Process each element
}
}
int main() {
int data[] = {1, 2, 3, 4, 5};
iterativeSolution(data, 5);
return 0;
}using System;
using System.Collections.Generic;
public class IterativeSolution {
public static void IterativeSolutionMethod(List<int> data) {
foreach(int num in data) {
Console.Write(num + " "); // Process each element
}
}
public static void Main(string[] args) {
List<int> data = new List<int>() {1, 2, 3, 4, 5};
IterativeSolutionMethod(data);
}
}The Python solution employs a simple for-loop to iterate over the list and print each number.
Time Complexity: O(n)
Space Complexity: O(1)
Approach 2: Approach 2: Recursive Solution
This approach leverages recursion to solve the problem. It is particularly useful when the problem can be broken down into smaller subproblems of the same nature.
def recursive_solution(data, index):
if index == len(data):
return
print(data[index], end=' ') # Process each element
recursive_solution(data, index + 1)
if __name__ == "__main__":
data = [1, 2, 3, 4, 5]
recursive_solution(data, 0)import java.util.List;
public class RecursiveSolution {
public static void recursiveSolution(List<Integer> data, int index) {
if (index == data.size()) return;
System.out.print(data.get(index) + " "); // Process each element
recursiveSolution(data, index + 1);
}
public static void main(String[] args) {
List<Integer> data = List.of(1, 2, 3, 4, 5);
recursiveSolution(data, 0);
}
}#include <iostream>
#include <vector>
void recursiveSolution(std::vector<int>& data, int index) {
if (index == data.size()) return;
std::cout << data[index] << " "; // Process each element
recursiveSolution(data, index + 1);
}
int main() {
std::vector<int> data = {1, 2, 3, 4, 5};
recursiveSolution(data, 0);
return 0;
}function recursiveSolution(data, index) {
if (index === data.length) return;
console.log(data[index]); // Process each element
recursiveSolution(data, index + 1);
}
let data = [1, 2, 3, 4, 5];
recursiveSolution(data, 0);#include <stdio.h>
void recursiveSolution(int data[], int index, int size) {
if (index == size) return;
printf("%d ", data[index]); // Process each element
recursiveSolution(data, index + 1, size);
}
int main() {
int data[] = {1, 2, 3, 4, 5};
recursiveSolution(data, 0, 5);
return 0;
}using System;
using System.Collections.Generic;
public class RecursiveSolution {
public static void RecursiveSolutionMethod(List<int> data, int index) {
if (index == data.Count) return;
Console.Write(data[index] + " "); // Process each element
RecursiveSolutionMethod(data, index + 1);
}
public static void Main(string[] args) {
List<int> data = new List<int>() {1, 2, 3, 4, 5};
RecursiveSolutionMethod(data, 0);
}
}Python's recursive solution involves processing an element and recursively calling for the next one.
Time Complexity: O(n)
Space Complexity: O(n)
Approach 3: Brute Force
We notice that the length of the array nums is no more than 200. Therefore, we can directly enumerate i, j, k, and check whether they meet the conditions. If they do, we increment the count of the triplet.
The time complexity is O(n^3), where n is the length of the array nums. The space complexity is O(1).
function arithmeticTriplets(nums: number[], diff: number): number {
const n = nums.length;
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let j = i + 1; j < n; ++j) {
for (let k = j + 1; k < n; ++k) {
if (nums[j] - nums[i] === diff && nums[k] - nums[j] === diff) {
++ans;
}
}
}
}
return ans;
}func arithmeticTriplets(nums []int, diff int) (ans int) {
n := len(nums)
for i := 0; i < n; i++ {
for j := i + 1; j < n; j++ {
for k := j + 1; k < n; k++ {
if nums[j]-nums[i] == diff && nums[k]-nums[j] == diff {
ans++
}
}
}
}
return
}Approach 4: Array or Hash Table
We can first store the elements of nums in a hash table or array vis. Then, for each element x in nums, we check if x+diff and x+diff+diff are also in vis. If they are, we increment the count of the triplet.
After the enumeration, we return the answer.
The time complexity is O(n) and the space complexity is O(n), where n is the length of the array nums.
function arithmeticTriplets(nums: number[], diff: number): number {
const vis: boolean[] = new Array(301).fill(false);
for (const x of nums) {
vis[x] = true;
}
let ans = 0;
for (const x of nums) {
if (vis[x + diff] && vis[x + diff + diff]) {
++ans;
}
}
return ans;
}func arithmeticTriplets(nums []int, diff int) (ans int) {
vis := [301]bool{}
for _, x := range nums {
vis[x] = true
}
for _, x := range nums {
if vis[x+diff] && vis[x+diff+diff] {
ans++
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Solution | Time Complexity: O(n) |
| Approach 2: Recursive Solution | Time Complexity: O(n) |
| Brute Force | – |
| Array or Hash Table | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Iterative Hash Set Enumeration | O(n) | O(n) | Best general solution. Efficient when constant-time membership checks are available. |
| Recursive Enumeration | O(n) | O(n) | Useful for demonstrating recursion patterns or practicing recursive traversal. |
Frequently asked questions
Is Number of Arithmetic Triplets easy or hard?
Number of Arithmetic Triplets is classified as an Easy problem on LeetCode with a high acceptance rate. The challenge mainly involves recognizing the arithmetic progression pattern and applying a hash set for efficient lookup.
How to solve Number of Arithmetic Triplets in O(n)?
Store all array values in a hash set. For each number x in nums, check if x + diff and x + 2*diff exist in the set. Every successful check forms one arithmetic triplet, so increment the count. The array is strictly increasing, which guarantees valid index ordering.
Number of Arithmetic Triplets Python or Java solution?
Most implementations use a set in Python or a HashSet in Java. Iterate through nums and check if num + diff and num + 2*diff exist in the set. The logic remains identical across Python, Java, C++, C#, and JavaScript.
What is the best approach for Number of Arithmetic Triplets?
The most efficient approach uses a hash set to check whether required elements exist. Insert all numbers into a set, then iterate through the array and verify if x + diff and x + 2*diff are present. This reduces the search to constant-time lookups and runs in O(n) time with O(n) space.
What data structure is used in Number of Arithmetic Triplets?
A hash set (hash table) is the key data structure. It enables O(1) average-time membership checks when verifying whether the next two numbers in the arithmetic progression exist.
What is the time complexity of Number of Arithmetic Triplets?
The optimal solution runs in O(n) time. Each element in the array is processed once, and two hash lookups are performed per element. Space complexity is O(n) due to storing the numbers in a hash set.
Is Number of Arithmetic Triplets asked at Google Amazon or Meta?
Arithmetic progression and hash set lookup problems commonly appear in interviews at companies like Amazon, Google, and Meta. Variations of this question test pattern recognition, hash table usage, and efficient array traversal.