Number of Arithmetic Triplets
EasyPrompt
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.
Approaches
3 approaches with complexity analysis and trade-offs.
The brute-force approach is the most straightforward solution. It involves iterating through every possible triplet of elements in the array and checking if they satisfy the conditions for an arithmetic triplet.
Algorithm
- Initialize a counter
countto 0. - Use three nested loops to iterate through all possible combinations of indices
(i, j, k)such thati < j < k. - The outer loop for
iruns from0ton-3. - The middle loop for
jruns fromi+1ton-2. - The inner loop for
kruns fromj+1ton-1. - Inside the innermost loop, check if
nums[j] - nums[i] == diffandnums[k] - nums[j] == diff. - If both conditions are met, increment
count. - After the loops complete, return
count.
Walkthrough
We can use three nested loops to generate all unique triplets of indices (i, j, k) where i < j < k. For each generated triplet, we access the corresponding numbers nums[i], nums[j], and nums[k]. We then check if they form an arithmetic progression with the given common difference diff. Specifically, we test if nums[j] - nums[i] == diff and nums[k] - nums[j] == diff. If both conditions hold true, we've found a valid arithmetic triplet and we increment a counter. After checking all possible triplets, the final value of the counter is the answer.
class Solution { public int arithmeticTriplets(int[] nums, int diff) { int count = 0; int n = nums.length; for (int i = 0; i < n; i++) { for (int j = i + 1; j < n; j++) { for (int k = j + 1; k < n; k++) { if (nums[j] - nums[i] == diff && nums[k] - nums[j] == diff) { count++; } } } } return count; }}Complexity
Time
O(n^3), where `n` is the number of elements in `nums`. The three nested loops result in a cubic time complexity as we check every possible triplet.
Space
O(1), as it only uses a constant amount of extra space for loop variables and the counter.
Trade-offs
Pros
Simple to understand and implement.
Requires no extra space, aside from a few variables.
Cons
Highly inefficient with a time complexity of O(n^3).
May be too slow for larger input sizes, though it passes for the given constraints.
This approach improves upon the brute-force method by reducing the complexity from cubic to quadratic. Instead of three nested loops, we can use two. The idea is to fix the middle element of a potential triplet and then search for the first and third elements on its left and right sides, respectively.
Algorithm
- Initialize a counter
countto 0. - Iterate through the array with an index
jfrom1ton-2, consideringnums[j]as the middle element of a potential triplet. - For each
j, search for anums[i]to its left (i < j) such thatnums[j] - nums[i] == diff. - Also, search for a
nums[k]to its right (k > j) such thatnums[k] - nums[j] == diff. - This can be done with two separate inner loops, one scanning from
0toj-1and the other fromj+1ton-1. - If both such elements are found, increment
count. - Return
countafter the main loop finishes.
Walkthrough
We iterate through the array with an index j from 1 to n-2. For each nums[j], we treat it as the middle element of a potential triplet. Then, we need to verify the existence of two other numbers: nums[j] - diff and nums[j] + diff. Since the array is strictly increasing and we need i < j < k, the element nums[j] - diff must appear at an index i < j, and nums[j] + diff must appear at an index k > j. We can use two separate linear scans for each j: one from index 0 to j-1 to find the first element, and another from j+1 to n-1 to find the third. If both elements are found, we increment our count.
class Solution { public int arithmeticTriplets(int[] nums, int diff) { int count = 0; int n = nums.length; for (int j = 1; j < n - 1; j++) { boolean foundFirst = false; for (int i = 0; i < j; i++) { if (nums[j] - nums[i] == diff) { foundFirst = true; break; } } if (foundFirst) { boolean foundThird = false; for (int k = j + 1; k < n; k++) { if (nums[k] - nums[j] == diff) { foundThird = true; break; } } if (foundThird) { count++; } } } return count; }}Complexity
Time
O(n^2). The outer loop runs `n` times. For each iteration, the two inner linear scans take O(j) and O(n-j) time respectively, leading to an overall quadratic time complexity.
Space
O(1), as it only uses a few variables for counting and loop indices.
Trade-offs
Pros
More efficient than the O(n^3) brute-force approach.
Still maintains a low space complexity.
Cons
Still not the most optimal solution as it has a quadratic time complexity.
Can be inefficient for very large arrays.
The most efficient solution utilizes a hash set to achieve constant-time lookups. By trading extra space for time, we can reduce the overall time complexity to linear. The core idea is to keep track of the numbers encountered so far and, for each new number, check if it can complete an arithmetic triplet with numbers seen previously.
Algorithm
- Initialize an empty hash set,
seen. - Initialize a counter
countto 0. - Iterate through each number
numin thenumsarray. - For each
num, check if the hash setseenalready containsnum - diffandnum - 2 * diff. - If both are present, it signifies that we have found a valid arithmetic triplet where
numis the third element. Incrementcount. - After the check, add the current
numto theseenset to make it available for subsequent elements. - After iterating through all numbers, return
count.
Walkthrough
This approach involves a single pass through the nums array. We use a hash set, let's call it seen, to store the numbers we have visited. As we iterate through each number num in nums, we treat it as the potential third element (nums[k]) of a triplet. For this to be true, the first two elements, nums[i] = num - 2 * diff and nums[j] = num - diff, must have appeared earlier in the array. We can check for their existence in our seen set in O(1) average time. If both are found in the set, we increment our triplet counter. After checking, we add the current num to the seen set. This single-pass strategy implicitly handles the i < j < k condition because we only find a triplet when processing num after its preceding elements have already been added to the set.
import java.util.HashSet;import java.util.Set; class Solution { public int arithmeticTriplets(int[] nums, int diff) { Set<Integer> seen = new HashSet<>(); int count = 0; for (int num : nums) { if (seen.contains(num - diff) && seen.contains(num - 2 * diff)) { count++; } seen.add(num); } return count; }}Complexity
Time
O(n). We iterate through the array once, and each operation within the loop (hash set lookups and insertion) takes O(1) on average.
Space
O(n), as the hash set may store up to `n` unique elements from the input array.
Trade-offs
Pros
Optimal time complexity of O(n).
Elegant and concise implementation, especially the single-pass version.
Cons
Requires extra space to store the elements in the hash set.
Solutions
Solution
class Solution {public int arithmeticTriplets(int[] nums, int diff) { int ans = 0; int n = nums.length; for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { if (nums[j] - nums[i] == diff && nums[k] - nums[j] == diff) { ++ans; } } } } return ans; }}class Solution {public: int arithmeticTriplets(vector<int> &nums, int diff) { int ans = 0; int n = nums.size(); for (int i = 0; i < n; ++i) { for (int j = i + 1; j < n; ++j) { for (int k = j + 1; k < n; ++k) { if (nums[j] - nums[i] == diff && nums[k] - nums[j] == diff) { ++ans; } } } } return ans; }};class Solution: def arithmeticTriplets(self, nums: List[int], diff: int) -> int: return sum( b - a == diff and c - b == diff for a, b, c in combinations(nums, 3))Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.