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.
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; }}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.