Table of Contents

## Problem Statement :

Arithmetic Slices II – Subsequence LeetCode Solution – Given an integer array of 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 :

**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 :**

## Observation :

- To determine an arithmetic sequence, we need at least two parameters: the first element of the sequence, and the common difference.
- If the first term of an arithmetic sequence is a1 and the common difference of successive members is d, then the n-th term of the sequence (an) is given by:

`an = a1 + (n-1)d`

## Approach :

- As we need to find the arithmetic subsequence i.e. elements of an array should be in arithmetic progression no matter they are contiguous or non-contiguous.
We will create an array of maps to store the frequency of difference of an element with respect to its previous elements.

In the original definition of

**arithmetic subsequence**, the length of the subsequence must be at least 3. But we are defining new subsequences that are**weak subsequences**of only**length 2**.frequencyArrayMap[i] stores the number of weak arithmetic subsequences that end with nums[i] and its common difference is diff.

A weak arithmetic sequence has two characteristics that we are defining:

- For any pair i,j (i != j) nums[i] and nums[j] can always form a weak arithmetic subsequence.
- If we add a new element to a weak arithmetic sequence, the new sequence must be an arithmetic sequence, because the new sequence has become the original arithmetic sequence of at least length 3.

Now for each nums[i], we will find the nums[j] forming a weak arithmetic sequence of length two.

For the nums[j], we will iterate from 0 to less than i.

In the FrequencyMapArray, which already stores the common difference of two elements nums[i] and nums[j], if we will find the same common difference for different pairs then we will add that frequency to our answer.

## Code for Arithmetic Slices II – Subsequence :

**Java Code :**

class Solution { public int numberOfArithmeticSlices(int[] nums) { int n = nums.length; long ans = 0; Map<Integer, Integer>[] frequencyArrayMap = new Map[n]; for(int i=0;i<n;i++){ frequencyArrayMap[i]=new HashMap<>(); } for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ long commondiff = (long)nums[i]-(long)nums[j]; if(commondiff<Integer.MIN_VALUE || commondiff> Integer.MAX_VALUE)continue; int diff =(int)commondiff; int prevFreq=frequencyArrayMap[j].getOrDefault(diff,0); int currFreq=frequencyArrayMap[i].getOrDefault(diff,0); ans+=prevFreq; frequencyArrayMap[i].put(diff,prevFreq+currFreq+1); } } return (int)ans; } }

**C++ Code :**

#define LL long long class Solution { public: int numberOfArithmeticSlices(vector<int>& nums) { int n = nums.size(); LL ans = 0; vector<map<int,int>>frequencyArrayMap(n); for(int i=0;i<n;i++){ for(int j=0;j<i;j++){ LL commondiff = (LL)nums[i]-(LL)nums[j]; if(commondiff<= INT_MIN || commondiff>= INT_MAX)continue; int diff =(int)commondiff; int prevFreq =0; int currFreq=0; if(frequencyArrayMap[j].find(diff) != frequencyArrayMap[j].end()){ prevFreq = frequencyArrayMap[j][diff]; currFreq = frequencyArrayMap[i][diff]; ans += prevFreq; frequencyArrayMap[i][diff] = currFreq + prevFreq + 1; } else{ frequencyArrayMap[i][diff]++; } } } return (int)ans; } };

## Complexity Analysis for Arithmetic Slices II – Subsequence LeetCode Solution:

**Time Complexity**

** O(n2) ** , as we are using two loops.

**Space Complexity **

** O(n2) ** For each num [i], we need to store at most

**distinct common differences, so the total space complexity is**

`n`

**$O(n^_{2}).$**