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 <= 50nums is strictly increasing.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.
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.
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.
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.
Time Complexity: O(n)
Space Complexity: O(n), due to recursion stack space.
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).
Python
Java
C++
Go
TypeScript
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.
Python
Java
C++
Go
TypeScript
| Approach | Complexity |
|---|---|
| Approach 1: Iterative Solution | Time Complexity: O(n), where n is the number of elements in the array. |
| Approach 2: Recursive Solution | Time Complexity: O(n) |
| Brute Force | — |
| Array or Hash Table | — |
| 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. |
Leetcode 2367. Number of Arithmetic Triplets | Weekly Contest 305. Easy • Code with Alisha • 5,652 views views
Watch 9 more video solutions →Practice Number of Arithmetic Triplets with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor