Leetcode Arithmetic Slices II – Subsequence problem solution

YASH PAL,

In this Leetcode Arithmetic Slices II – Subsequence problem solution you have 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.

  1. For example, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.
  2. 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.

  1. 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 a 32-bit integer.

Leetcode Arithmetic Slices II - Subsequence problem solution

Problem solution in Python.

class Solution:
    def numberOfArithmeticSlices(self, A: List[int]) -> int:
        dic={}
        for i in range(len(A)):
            dic[i]={}
        ans=0
        for i in range(len(A)):
            for j in range(i):
                d=A[i]-A[j]
                if d not in dic[j]:
                    if d in dic[i]:
                        dic[i][d]+=1
                    else:
                        dic[i][d]=1
                else:
                    if d not in dic[i]:
                        dic[i][d]=dic[j][d]+1
                        ans+=dic[j][d]
                    else:
                        dic[i][d]+=dic[j][d]+1
                        ans+=dic[j][d]
        return ans

Problem solution in Java.

public int numberOfArithmeticSlices(int[] A) {
        int l = A.length;
        if(l <3){
            return 0;
        int[] left = new int[l];
        int[] right = new int[l];
        left[0] = 0;
        right[l-1] = 0;
        for(int i=1;i<l;i++){
            left[i] = A[i] - A[i-1];
        }
        
        for(int i=l-2;i>=0;i--){
            right[i] =  A[i+1] - A[i];
        }

        int prev = 0;
        int[] result = new int[l];
        for(int i=1;i<l-1;i++){
            if(right[i] == left[i]){
                result[i] = 1;
                    if(right[i-1] == left[i-1]){
                        result[i] = result[i]+result[i-1];
                    }
            }
        }
        
        int sum=0;
        for(int i=0;i<l;i++){
            sum+=result[i];
        }
        
        return sum;
    }

Problem solution in C++.

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int ans = 0, n = size(nums); 
        vector<unordered_map<int, int>> freq(n); 
        for (size_t i = 0; i < n; ++i) {
            for (size_t ii = 0; ii < i; ++ii) {
                long temp = (long) nums[i] - nums[ii]; 
                if (temp > INT_MAX || temp < INT_MIN) continue;
                int diff = nums[i] - nums[ii]; 
                ans += freq[ii][diff]; 
                freq[i][diff] += 1 + freq[ii][diff]; 
            }
        }
        return ans; 
    }
};

coding problems solutions