Arithmetic Slices Ii Subsequence - Leetcode Solution

Arithmetic Slices II - Subsequence problem can be solved using dynamic programming approach. The problem statement describes that we have to find the number of arithmetic subsequence which have a length of at least 3. An arithmetic sequence is a sequence where the difference between two consecutive elements is the same throughout the sequence. For example, 1, 3, 5, 7 is an arithmetic sequence with a common difference of 2.

To solve this problem, we will use dynamic programming to build a table of counts. The table will keep track of the number of arithmetic subsequences that end at each position in the input array. We choose this because when we add an element to the table, we can check if it can extend any previous subsequences.

Algorithm:

1. Create a dictionary dp with default value 0 to keep track of the counts of arithmetic subsequences.
2. Loop through the input array, for each element a[i]: a. Loop through the array from 0 to i-1, for each element a[j]: i. Calculate the arithmetic difference between a[i] and a[j]: diff = a[i] - a[j] ii. Check if the dictionary dp already has a key (i, diff) then increment the value by dp[(j, diff)] iii. Increment dp[(i, diff)] by dp[(j, diff)] + 1
3. In the above step, we are calculating the count of arithmetic subsequences ending at position i whose last element has a difference diff with element i and we do this by looping over all the indices j less than i and forming a valid arithmetic subsequence ending at j with difference diff and calculate the value dp[j, diff] for them. Now, we can extend all these subsequences by adding i itself as the next element in them thus we increment dp[i, diff] by value of dp[j, diff] +1 for all such subsequences.
4. Finally loop through the dictionary dp, summing all the values >=3. This will give us the total count of arithmetic subsequences of length >=3.

Let's implement it in Python:

def numberOfArithmeticSlices(nums):
    dp = {}
    for i in range(len(nums)):
        for j in range(i):
            diff = nums[i] - nums[j]
            if (j, diff) in dp:
                dp[(i, diff)] = dp[(j, diff)] + dp.get((i, diff), 0)
            dp[(i, diff)] = dp.get((i, diff), 0) + 1
    count = 0
    for key in dp:
        if dp[key] >= 3:
            count += dp[key]
    return count

Time Complexity: The nested loops run n^2 times, so the time complexity is O(n^2).

Space Complexity: We are using a dictionary to store the dp table with a maximum size of n^2, so the space complexity is O(n^2).

Overall, this is a very efficient and optimal solution for the given problem.

1