# Number of Arithmetic Triplets
**Difficulty:** EASY
[External](https://leetcode.com/problems/number-of-arithmetic-triplets)
Canonical: https://scaleengineer.com/dsa/problems/number-of-arithmetic-triplets
**Patterns:** [Two Pointers](https://scaleengineer.com/dsa/patterns/two-pointers), [Enumeration](https://scaleengineer.com/dsa/patterns/enumeration)
**Data structures:** Array, Hash Table
---
## Problem
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`, and
* `nums[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 <= 200`
* `0 <= nums[i] <= 200`
* `1 <= diff <= 50`
* `nums` is **strictly** increasing.

# Approaches
## Brute Force with Triple Nested Loops
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Use three nested loops to iterate through all possible combinations of indices `(i, j, k)` such that `i < j < k`.
- The outer loop for `i` runs from `0` to `n-3`.
- The middle loop for `j` runs from `i+1` to `n-2`.
- The inner loop for `k` runs from `j+1` to `n-1`.
- Inside the innermost loop, check if `nums[j] - nums[i] == diff` and `nums[k] - nums[j] == diff`.
- If both conditions are met, increment `count`.
- After the loops complete, return `count`.

## Optimized Search with Two Loops
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize a counter `count` to 0.
- Iterate through the array with an index `j` from `1` to `n-2`, considering `nums[j]` as the middle element of a potential triplet.
- For each `j`, search for a `nums[i]` to its left (`i < j`) such that `nums[j] - nums[i] == diff`.
- Also, search for a `nums[k]` to its right (`k > j`) such that `nums[k] - nums[j] == diff`.
- This can be done with two separate inner loops, one scanning from `0` to `j-1` and the other from `j+1` to `n-1`.
- If both such elements are found, increment `count`.
- Return `count` after the main loop finishes.

## Optimal Solution using a Hash Set
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.
**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.
**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.
### Explanation
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.

```java
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;
    }
}
```
### Algorithm
- Initialize an empty hash set, `seen`.
- Initialize a counter `count` to 0.
- Iterate through each number `num` in the `nums` array.
- For each `num`, check if the hash set `seen` already contains `num - diff` and `num - 2 * diff`.
- If both are present, it signifies that we have found a valid arithmetic triplet where `num` is the third element. Increment `count`.
- After the check, add the current `num` to the `seen` set to make it available for subsequent elements.
- After iterating through all numbers, return `count`.

# Solutions
### Java

```java
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;
  }
}

```

### CPP

```cpp
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;
  }
};

```

### Python

```python
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))

```