Number of Arithmetic Triplets

The problem is asking to count the number of unique arithmetic triplets in the given list of numbers. A triplet is arithmetic if the difference between the second and first element is equal to the difference between the third and second element, and this difference equals a given value diff.

Here’s an example: consider the list [1, 4, 7, 10] and diff = 3. The arithmetic triplets in this case would be (1, 4, 7) and (4, 7, 10), because in both cases the difference between each consecutive pair of elements is 3. So the output would be 2, because there are two such triplets.

To be considered a triplet, the three numbers have to be in the correct order in the array, not just any three numbers. For example, in the list [1, 7, 4, 10] with diff = 3, there are no arithmetic triplets, because even though 1, 4, and 7 could form a triplet, they are not in the right order in the array.

Also, the array nums is strictly increasing, which means that each number is larger than the previous number.

The goal is to find an efficient way to count all such triplets in the given array.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

from typing import List

class Solution:
    def arithmeticTriplets(self, nums: List[int], diff: int) -> int:
        cnt = [0]*201
        res = 0
        for n in nums:
            if n >= 2 * diff:
                res += cnt[n - diff] and cnt[n - 2 * diff]
            cnt[n] = 1
        return res

The Python function arithmeticTriplets is designed to find the count of arithmetic triplets in a given list of numbers nums where the common difference is diff.

An arithmetic triplet is a sequence of three numbers where the difference between consecutive numbers is constant. For example, in the sequence [3, 5, 7], the difference between consecutive numbers is 2, making it an arithmetic triplet.

Here’s how the function works:

  1. The function starts by initializing a list cnt of size 201 with all elements set to 0. This list will be used to store the presence of each number in nums.

  2. It also initializes res to 0. This variable will hold the final count of arithmetic triplets.

  3. Then, it iterates over all the numbers in nums. For each number n, it checks if n is greater than or equal to 2 * diff. If it is, it means n can potentially be the third number in an arithmetic triplet.

  4. If n is greater than or equal to 2 * diff, the function increments res if the numbers n - diff and n - 2 * diff are present in nums. The presence of these numbers is checked using the cnt list.

  5. After this, it marks the presence of n in the cnt list by setting cnt[n] to 1.

  6. Finally, it returns res, which is the count of arithmetic triplets in nums.

This function effectively uses a counting array to keep track of the presence of numbers in nums and finds the count of arithmetic triplets in a single pass, resulting in a time complexity of O(n), where n is the number of elements in nums. The space complexity is O(1) as the size of the cnt list is fixed.

Q&A

Can u tell me why check n >= 2 * diff ?

In an arithmetic progression or sequence, the difference between consecutive terms is constant. If we consider a triplet (a, b, c) to be in arithmetic progression, it must satisfy the condition that b - a = c - b, where b - a and c - b are the common differences.

In the context of this problem, we’re looking for triplets where the common difference is diff. So, we need b - a = diff and c - b = diff. If we rearrange the terms, we get b = a + diff and c = b + diff = a + 2 * diff.

Now, when we’re iterating over nums and checking for each number n, n could be the third term of an arithmetic triplet (i.e., n = c). Before checking if n forms a triplet with two previous numbers, we need to ensure that the two previous numbers (i.e., a and b) can exist. And for a and b to exist, n should be at least 2 * diff (since n = a + 2 * diff).

So, the check n >= 2 * diff is to ensure that n can potentially be the third number in an arithmetic triplet. If n is less than 2 * diff, it cannot be the third number in a triplet with a common difference of diff.