Arithmetic Slices II – Subsequence LeetCode Solution

Difficulty Level Hard
Frequently asked in Adobe Google Uber
BaiduViews 2347

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.

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.

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:

1.  For any pair i,j (i != j) nums[i] and nums[j] can always form a weak arithmetic subsequence.
2.  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 n distinct common differences, so the total space complexity is

Translate »