2367. Number of Arithmetic Triplets
Problem Description
You are given an array of distinct integers which is in increasing order and a positive integer representing the difference value, diff
. The goal is to find out how many unique triplets of indices (i, j, k)
within the array satisfy two conditions: first, nums[j] - nums[i]
is equal to diff
, and second, nums[k] - nums[j]
is equal to diff
as well, with the indices following the relationship of i < j < k
. This is essentially looking for sequences of three numbers that form an arithmetic progression with a common difference of diff
.
Intuition
The intuition behind the solution involves understanding that for an arithmetic triplet to exist for a number x
(nums[i]
), there must be two other numbers x + diff
(nums[j]
) and x + diff * 2
(nums[k]
) present in the array. The solution utilizes a set to store the numbers for constant-time lookups, which makes checking the existence of x + diff
and x + diff * 2
efficient.
The approach is as follows:
- Convert the list of numbers into a set for faster lookup. This is beneficial because we want to be able to quickly check if a number
+ diff
exists in the original array. - Iterate over each number in the array (which is already in increasing order) and for each number
x
, check if bothx + diff
andx + diff * 2
are present in the set. - Sum up the results of the checks for each element. If for a given number
x
, bothx + diff
andx + diff * 2
are found, this indicates the existence of an arithmetic triplet, so we count it. - The sum gives the total count of such unique triplets in the array.
This method is efficient because we capitalize on the properties of sets and the given ordered nature of the array to avoid unnecessary computations. By doing a single pass through the array and checking for the presence of the other two elements in the triplet, we achieve a solution that is simple and effective.
Learn more about Two Pointers patterns.
Solution Approach
The solution is implemented using a set data structure and a single for-loop iteration through the array. Here is the breakdown of how the solution works step by step:
-
Convert the
nums
array into a set calledvis
which stands for visited or seen. The conversion to a set is critical because it allows forO(1)
time complexity lookups to check if an element exists within the array.1vis = set(nums)
-
Use list comprehension combined with the
sum
function to iterate over each numberx
innums
. The iteration results in a boolean expression for each number which checks if both the next two numbers in the arithmetic sequence are present in the setvis
. For eachx
innums
, ifx + diff
andx + diff * 2
exist invis
, the condition isTrue
and contributes 1 to the sum, otherwise, it contributes 0.1sum(x + diff in vis and x + diff * 2 in vis for x in nums)
-
For each iteration, the algorithm checks for the two required conditions:
x + diff
is invis
: This checks if there is another number ahead in the array that isdiff
greater than the current numberx
. This is looking for thej
index such thatnums[j] - nums[i] == diff
.x + diff * 2
is invis
: This checks if there is a number that is twice thediff
greater than the current numberx
. This is looking for thek
index such thatnums[k] - nums[j] == diff
.
-
The
sum
function then adds up the results from the list comprehension. EachTrue
represents a valid arithmetic triplet, and the sum is therefore the total count of unique arithmetic triplets in the array.
The pattern used here is effectively checking each possible starting point of an arithmetic triplet and rightly assuming that due to the strictly increasing nature of the inputs, if an x + diff
and x + diff * 2
exist, they will be part of a valid arithmetic triplet. The use of set for constant-time lookups and list comprehension for concise code makes the implementation both efficient and readable.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's illustrate the solution approach with a small example. Suppose our array of distinct integers is nums = [1, 3, 5, 7, 9]
, and the given difference value is diff = 2
.
Following the steps outlined in the solution approach:
-
We first convert the
nums
array into a setvis
to make element lookups more efficient:1nums = [1, 3, 5, 7, 9] 2vis = set(nums) # vis is now {1, 3, 5, 7, 9}
-
Next, we use list comprehension and the
sum
function to iterate over each number innums
. For each numberx
, we check ifx + diff
andx + diff * 2
are present in the setvis
.Here's what happens for each element of
nums
:-
For
x = 1
: Check if1 + 2
and1 + 4
are invis
. This isTrue
because both3
and5
are invis
. -
For
x = 3
: Check if3 + 2
and3 + 4
are invis
. This isTrue
because both5
and7
are invis
. -
For
x = 5
: Check if5 + 2
and5 + 4
are invis
. This isTrue
because both7
and9
are invis
. -
For
x = 7
: Check if7 + 2
and7 + 4
are invis
. This isFalse
since9
is invis
but11
is not. -
For
x = 9
: Check if9 + 2
and9 + 4
are invis
. This isFalse
since neither11
nor13
is invis
.
The above checks can be summed up with the following line of code:
1sum(x + diff in vis and x + diff * 2 in vis for x in nums)
-
-
As we iterate over the array, we find that
x = 1
,x = 3
, andx = 5
satisfy both conditions of being a valid starting point for an arithmetic triplet with a common difference ofdiff
. Therefore, for these elements, the corresponding boolean will beTrue
. -
The
sum
function will sum theseTrue
values. In our example, we have threeTrue
values corresponding to starting points1
,3
, and5
, resulting in a sum of3
.
Therefore, there are three unique triplets that form an arithmetic progression with a common difference of 2
in the array nums = [1, 3, 5, 7, 9]
.
This walkthrough demonstrates the utility of the set data structure for lookups and the effectiveness of iterating through the ordered list to identify valid arithmetic triplets.
Solution Implementation
1from typing import List
2
3class Solution:
4 def arithmeticTriplets(self, nums: List[int], diff: int) -> int:
5 # Create a set from the list for constant time look-up.
6 seen_numbers = set(nums)
7
8 # Count the number of valid arithmetic triplets
9 # An arithmetic triplet is a sequence of three numbers where
10 # the difference between consecutive numbers is equal to diff.
11 # Here it checks if for a given number x in nums, both x + diff and
12 # x + 2 * diff are present in nums. If so, that contributes to one valid triplet.
13 triplet_count = sum(x + diff in seen_numbers and x + 2 * diff in seen_numbers for x in nums)
14
15 # Return the total count of triplets found.
16 return triplet_count
17
1class Solution {
2 // Function to find the number of arithmetic triplets in an array
3 public int arithmeticTriplets(int[] nums, int diff) {
4 // An array to keep track of the presence of elements up to the maximum possible value
5 boolean[] seen = new boolean[301];
6
7 // Mark the presence of each number in the 'seen' array
8 for (int num : nums) {
9 seen[num] = true;
10 }
11
12 // Initialize the count for arithmetic triplets
13 int count = 0;
14
15 // Iterate through the array to find arithmetic triplets
16 for (int num : nums) {
17 // Check if the two subsequent numbers (with the given difference 'diff') are present
18 if (seen[num + diff] && seen[num + 2 * diff]) {
19 // If both are present, we found an arithmetic triplet, increment the count
20 ++count;
21 }
22 }
23
24 // Return the total count of arithmetic triplets found
25 return count;
26 }
27}
28
1#include <vector>
2#include <bitset>
3
4class Solution {
5public:
6 // This function counts the number of arithmetic triplets in the array.
7 // An arithmetic triplet is a sequence of three numbers such that
8 // the difference between consecutive numbers is the same as 'diff'.
9 int arithmeticTriplets(vector<int>& nums, int diff) {
10 bitset<301> visitedNumbers; // Initialize a bitset where we will mark the numbers present in 'nums'.
11
12 // Mark all the numbers present in the 'nums' vector within the bitset 'visitedNumbers'.
13 for (int number : nums) {
14 visitedNumbers[number] = 1;
15 }
16
17 int countTriplets = 0; // Initialize counter for arithmetic triplets.
18
19 // Iterate through all the numbers in 'nums'.
20 for (int number : nums) {
21 // Check if there are two other numbers in the sequence that make an arithmetic triplet
22 // with the current 'number' and the given 'diff' (difference).
23 // Increases countTriplets when the two other numbers forming the triplet are present, i.e., when
24 // both 'number + diff' and 'number + 2 * diff' are set in the 'visitedNumbers' bitset.
25 countTriplets += visitedNumbers[number + diff] && visitedNumbers[number + 2 * diff];
26 }
27
28 return countTriplets; // Return the total number of arithmetic triplets found in 'nums'.
29 }
30};
31
1function arithmeticTriplets(nums: number[], diff: number): number {
2 // Initialize an array that will keep track of the presence of numbers within 'nums'
3 const visited: boolean[] = new Array(301).fill(false);
4
5 // Populate the 'visited' array with true at indexes that exist in the 'nums' array
6 for (const num of nums) {
7 visited[num] = true;
8 }
9
10 // Initialize a counter for the number of arithmetic triplets found
11 let tripletCount = 0;
12
13 // Iterate through the 'nums' array to find arithmetic triplets
14 for (const num of nums) {
15 // Check if the two successors (num+diff and num+2*diff) are present in 'nums'
16 if (visited[num + diff] && visited[num + 2 * diff]) {
17 // Increment the counter if both successors are found, signifying an arithmetic triplet
18 tripletCount++;
19 }
20 }
21
22 // Return the total count of arithmetic triplets
23 return tripletCount;
24}
25
Time and Space Complexity
Time Complexity
The given code traverses through all the elements in the nums
list once to construct the vis
set, and again it iterates through all elements of nums
in the return statement.
For each element x
in nums
, the code checks if x + diff
and x + diff * 2
are present in the vis
set. Looking up an element in a set has an average time complexity of O(1)
because sets in Python are implemented as hash tables.
Therefore, the overall time complexity is O(n)
where n
is the number of elements in nums
, since the set lookup operation is constant time on average, and we are doing this operation twice for each element in nums
.
Space Complexity
The space complexity of the code is determined by the additional data structures that are used. Here, a set vis
is created based on the elements of nums
. In the worst case, if all elements in nums
are unique, the vis
set will contain the same number of elements as nums
.
So, the space complexity would be O(n)
, where n
is the number of elements in nums
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which data structure is used to implement priority queue?
Recommended Readings
Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.