Skip to main content
Talentd

Number of Arithmetic Triplets - Solution & Explanation

EasyArrayHash TableTwo PointersEnumeration14 min readAsked at: Meta, Google
Practice this problem

Problem Statement

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, and
  • nums[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 <= 200
  • 0 <= nums[i] <= 200
  • 1 <= diff <= 50
  • nums is 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.

The C solution processes each element of the input array in a simple for-loop, demonstrating an iterative approach.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as we are using only a constant amount of extra space.

Try this approach in the editor →

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.

A recursive C solution where the function prints the current element and calls itself for the next index.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(n)
Space Complexity: O(n), due to recursion stack space.

Try this approach in the editor →

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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

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.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Iterative Solution

Time Complexity: O(n), where n is the number of elements in the array.
Space Complexity: O(1), as we are using only a constant amount of extra space.

Approach 2: Recursive Solution

Time Complexity: O(n)
Space Complexity: O(n), due to recursion stack space.

Brute Force—
Array or Hash Table—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Iterative Hash Set EnumerationO(n)O(n)Best general solution. Efficient when constant-time membership checks are available.
Recursive EnumerationO(n)O(n)Useful for demonstrating recursion patterns or practicing recursive traversal.

Video Solution

Leetcode 2367. Number of Arithmetic Triplets | Weekly Contest 305. Easy • Code with Alisha • 5,745 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Number of Arithmetic Triplets with our built-in code editor and test cases.

Practice on FleetCode
Previous

3Sum

Next

Maximum Value of an Ordered Triplet I