# Arithmetic Slices II - Subsequence
**Difficulty:** HARD
[External](https://leetcode.com/problems/arithmetic-slices-ii-subsequence)
Canonical: https://scaleengineer.com/dsa/problems/arithmetic-slices-ii-subsequence
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array
**Companies:** [Baidu](https://scaleengineer.com/companies/baidu), [Dunzo](https://scaleengineer.com/companies/dunzo)
---
## Problem
Given an integer array `nums`, return _the number of all the **arithmetic subsequences** of_ `nums`.

A sequence of numbers is called arithmetic if it consists of **at least three elements** and if the difference between any two consecutive elements is the same.

* For example, `[1, 3, 5, 7, 9]`, `[7, 7, 7, 7]`, and `[3, -1, -5, -9]` are arithmetic sequences.
* For example, `[1, 1, 2, 5, 7]` is not an arithmetic sequence.

A **subsequence** of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

* For example, `[2,5,10]` is a subsequence of `[1,2,1,**2**,4,1,**5**,**10**]`.

The test cases are generated so that the answer fits in **32-bit** integer.

**Example 1:**

**Input:** nums = [2,4,6,8,10]
**Output:** 7
**Explanation:** All arithmetic subsequence slices are:
[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

**Example 2:**

**Input:** nums = [7,7,7,7,7]
**Output:** 16
**Explanation:** Any subsequence of this array is arithmetic.

**Constraints:**

* `1 <= nums.length <= 1000`
* `-231 <= nums[i] <= 231 - 1`

# Approaches
## Brute Force with Three Nested Loops
This approach iterates through all possible pairs of elements `(nums[i], nums[j])` to serve as the first two elements of a potential arithmetic subsequence. For each pair, it calculates the common difference and then scans the rest of the array to find subsequent elements that extend this arithmetic sequence, counting each valid extension.
**Time:** O(N^3), due to three nested loops. The outer two loops select a pair of elements in O(N^2) time, and the inner loop scans the rest of the array in O(N) time. · **Space:** O(1), as we only use a few variables to store the count, difference, and next value, independent of the input size.
**Pros:** Simple to understand and implement.; Very low memory usage, requiring only O(1) extra space.
**Cons:** High time complexity of O(N^3) makes it too slow for the given constraints (N <= 1000) and will likely result in a 'Time Limit Exceeded' error.
### Explanation
The fundamental idea is to check every possible starting pair of an arithmetic sequence and then count how many ways it can be extended. We can fix the first two elements of a subsequence, say `nums[i]` and `nums[j]` where `i < j`. This determines the common difference `d = nums[j] - nums[i]`. With the first two elements and the difference fixed, the rest of the sequence is also fixed. The third element must be `nums[j] + d`, the fourth `nums[j] + 2*d`, and so on. We can iterate through the rest of the array (from index `j+1`) to find these subsequent elements. Each time we find a matching element, it forms a new arithmetic subsequence of length at least 3, so we increment our total count.

For example, if we have the subsequence `[a, b, c]`, this approach counts it when the starting pair is `(a, b)`. If there's another element `d` such that `[a, b, c, d]` is arithmetic, the subsequence `[a, b, d]` is not counted (as it's not arithmetic), but the extension that forms `[a, b, c, d]` is counted as a new valid subsequence. The subsequence `[b, c, d]` will be counted separately when the starting pair is `(b, c)`.

```java
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return 0;
        }
        int count = 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                long diff = (long)nums[j] - (long)nums[i];
                long next_val = (long)nums[j] + diff;
                for (int k = j + 1; k < n; k++) {
                    if ((long)nums[k] == next_val) {
                        count++;
                        next_val += diff;
                    }
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Initialize `total_count` to 0.
- Iterate `i` from `0` to `n-2`.
- Inside this loop, iterate `j` from `i+1` to `n-1`.
  - These two elements, `nums[i]` and `nums[j]`, form the first two elements of a potential arithmetic subsequence.
  - Calculate the common difference `diff = (long)nums[j] - nums[i]`.
  - The next element required to form a length-3 subsequence is `next_val = (long)nums[j] + diff`.
  - Iterate `k` from `j+1` to `n-1` to search for subsequent elements.
    - If `(long)nums[k]` is equal to `next_val`:
      - We have found an arithmetic subsequence of length at least 3 (e.g., `[nums[i], nums[j], nums[k]]`).
      - Increment `total_count`.
      - Update `next_val` to `next_val + diff` to continue searching for a longer subsequence with the same starting pair and difference.
- After all loops complete, return `total_count`.

## Dynamic Programming
This approach uses dynamic programming to efficiently count the arithmetic subsequences. We build up the solution by iterating through the array. For each element, we consider it as the potential end of an arithmetic subsequence and use a DP table (an array of hash maps) to store the number of arithmetic subsequences ending at a particular index with a specific common difference.
**Time:** O(N^2). We have two nested loops iterating up to `N`. The hash map operations (get and put) inside the loops take, on average, O(1) time. · **Space:** O(N^2). In the worst-case scenario, all differences `nums[i] - nums[j]` could be unique for all pairs `(i, j)`. The total number of entries across all hash maps in the `dp` array could be up to O(N^2).
**Pros:** Significantly more efficient than the brute-force approach with a polynomial time complexity.; It is guaranteed to pass within the time limits for the given constraints.
**Cons:** Higher space complexity compared to the brute-force approach.; The logic can be more complex to grasp initially.
### Explanation
Let `dp[i]` be a hash map where `dp[i][d]` stores the number of arithmetic subsequences of length **at least 2**, ending at index `i` with a common difference `d`. We need to count subsequences of length at least 3.

We iterate through the array with an index `i` from 0 to `n-1`. For each `i`, we iterate with a preceding index `j` from 0 to `i-1`. For each pair `(i, j)`, we calculate the difference `d = (long)nums[i] - (long)nums[j]`.

Any arithmetic subsequence ending at `nums[j]` with this same difference `d` can be extended by `nums[i]`. If there are `k = dp[j][d]` such subsequences (which must have length >= 2), extending them with `nums[i]` creates `k` new arithmetic subsequences of length >= 3. Therefore, we add `dp[j][d]` to our total result.

After that, we must update the DP state for index `i`. The number of arithmetic subsequences ending at `i` with difference `d` is the sum of:
1. The subsequences of length >= 2 ending at `j` with difference `d`, which are now extended (`dp[j][d]` of them).
2. The new subsequence of length 2 formed by `(nums[j], nums[i])` (which is 1).
So, we update `dp[i][d]` by adding `dp[j][d] + 1` to its current value.

```java
class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        if (n < 3) {
            return 0;
        }
        int totalCount = 0;
        // dp[i] is a map where key is the difference and value is the count of
        // arithmetic subsequences of length at least 2 ending at index i.
        HashMap<Long, Integer>[] dp = new HashMap[n];

        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
            for (int j = 0; j < i; j++) {
                long diff = (long) nums[i] - (long) nums[j];
                
                // Get count of subsequences ending at j with this difference.
                int countAtJ = dp[j].getOrDefault(diff, 0);
                
                // These countAtJ subsequences, when extended with nums[i],
                // form valid subsequences of length >= 3.
                totalCount += countAtJ;
                
                // Get current count of subsequences ending at i with this difference.
                int countAtI = dp[i].getOrDefault(diff, 0);
                
                // Update dp[i] for the current difference.
                // The new count is the sum of existing ones (countAtI), 
                // those extended from j (countAtJ), and the new pair (nums[j], nums[i]) (+1).
                dp[i].put(diff, countAtI + countAtJ + 1);
            }
        }
        return totalCount;
    }
}
```
### Algorithm
- Initialize `total_count = 0`.
- Create an array of HashMaps, `dp`, of size `n`. `dp[i]` will store `{difference: count}` for arithmetic subsequences ending at `nums[i]`.
- Loop `i` from `0` to `n-1`.
  - Initialize `dp[i]` as a new HashMap.
  - Loop `j` from `0` to `i-1`.
    - Calculate the difference `diff = (long)nums[i] - (long)nums[j]`.
    - Retrieve the number of arithmetic subsequences of length >= 2 ending at `j` with this `diff`: `count_at_j = dp[j].getOrDefault(diff, 0)`.
    - Each of these `count_at_j` subsequences can be extended by `nums[i]` to form a valid subsequence of length >= 3. Add this count to the `total_count`.
    - Now, update the map for the current index `i`. The number of subsequences ending at `i` with difference `diff` increases. The new count is the sum of what was already there (`dp[i].getOrDefault(diff, 0)`), the subsequences extended from `j` (`count_at_j`), and the new subsequence of length 2 formed by `(nums[j], nums[i])` (which adds 1).
    - `dp[i].put(diff, dp[i].getOrDefault(diff, 0) + count_at_j + 1)`.
- After the loops, return `total_count`.

# Solutions
### Java

```java
class Solution {
public
  int numberOfArithmeticSlices(int[] nums) {
    int n = nums.length;
    Map<Long, Integer>[] f = new Map[n];
    Arrays.setAll(f, k->new HashMap<>());
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        Long d = 1L * nums[i] - nums[j];
        int cnt = f[j].getOrDefault(d, 0);
        ans += cnt;
        f[i].merge(d, cnt + 1, Integer : : sum);
      }
    }
    return ans;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int numberOfArithmeticSlices(vector<int> &nums) {
    int n = nums.size();
    unordered_map<long long, int> f[n];
    int ans = 0;
    for (int i = 0; i < n; ++i) {
      for (int j = 0; j < i; ++j) {
        long long d = 1LL * nums[i] - nums[j];
        int cnt = f[j][d];
        ans += cnt;
        f[i][d] += cnt + 1;
      }
    }
    return ans;
  }
};

```

### Python

```python
class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int: f = [defaultdict(int) for _ in nums] ans = 0 for i, x in enumerate(nums): for j, y in enumerate(nums[: i]): d = x - y ans += f[j][d] f[i][d] += f[j][d] + 1 return ans

```