Code Implementation

class Solution:
    def numberOfArithmeticSlices(self, nums):
        from collections import defaultdict
        n = len(nums)
        dp = [defaultdict(int) for _ in range(n)]
        res = 0
        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                cnt = dp[j][diff]
                dp[i][diff] += cnt + 1
                res += cnt
        return res
      

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int n = nums.size();
        vector<unordered_map<long long, int>> dp(n);
        int res = 0;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                long long diff = (long long)nums[i] - (long long)nums[j];
                int cnt = dp[j].count(diff) ? dp[j][diff] : 0;
                dp[i][diff] += cnt + 1;
                res += cnt;
            }
        }
        return res;
    }
};
      

class Solution {
    public int numberOfArithmeticSlices(int[] nums) {
        int n = nums.length;
        Map<Long, Integer>[] dp = new HashMap[n];
        for (int i = 0; i < n; i++) {
            dp[i] = new HashMap<>();
        }
        int res = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long diff = (long)nums[i] - (long)nums[j];
                int cnt = dp[j].getOrDefault(diff, 0);
                dp[i].put(diff, dp[i].getOrDefault(diff, 0) + cnt + 1);
                res += cnt;
            }
        }
        return res;
    }
}
      

var numberOfArithmeticSlices = function(nums) {
    const n = nums.length;
    const dp = Array.from({length: n}, () => new Map());
    let res = 0;
    for (let i = 0; i < n; i++) {
        for (let j = 0; j < i; j++) {
            let diff = nums[i] - nums[j];
            let cnt = dp[j].get(diff) || 0;
            dp[i].set(diff, (dp[i].get(diff) || 0) + cnt + 1);
            res += cnt;
        }
    }
    return res;
};
      

Problem Description

Given an integer array nums, your task is to count the number of arithmetic subsequence slices in nums. An arithmetic subsequence slice is defined as a subsequence of at least three elements where the difference between every two consecutive elements is the same.

• A subsequence is a sequence that can be derived from another sequence by deleting some or no elements without changing the order of the remaining elements.
• The problem asks for the number of all possible arithmetic subsequences of length at least 3.
• Elements can be reused only as allowed by the subsequence property (i.e., you cannot use the same index twice).
• Constraints:
  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1

Thought Process

To solve this problem, we first consider the brute-force approach: generate every possible subsequence of length at least 3, check if it is arithmetic, and count it if so. However, the number of subsequences grows exponentially with the length of the array, making this approach infeasible for large arrays.

We need a more efficient way. By observing that any arithmetic subsequence of length at least 3 is built upon pairs (of length 2) with a common difference, we can try to count, for each pair, how many longer arithmetic subsequences can be formed by extending this pair. This suggests a dynamic programming approach, where we keep track of the count of arithmetic subsequences ending at each index with a certain difference.

The key insight is that for each number, we can look back at all previous numbers, compute the difference, and update our count of arithmetic slices accordingly. By using hash maps (dictionaries) to store the counts for each possible difference at each index, we can efficiently build up the answer without explicitly generating all subsequences.

Solution Approach

We use dynamic programming with hash maps to efficiently count all arithmetic subsequence slices:

1. DP Structure: For each index i in nums, we maintain a hash map dp[i] where dp[i][d] is the number of arithmetic subsequences ending at index i with common difference d.
2. Iterate Over Pairs: For every pair of indices (j, i) with j < i, calculate the difference d = nums[i] - nums[j].
3. Update Counts:
   • If dp[j][d] exists, it represents the number of arithmetic subsequences ending at j with difference d. We can extend each of these by nums[i] to form longer subsequences.
   • Each pair (j, i) can at least start a new sequence of length 2, so we increment dp[i][d] by 1.
   • We also add dp[j][d] to dp[i][d] to account for extending existing subsequences.
4. Count Valid Slices: Only subsequences of length at least 3 count towards the result. Since new pairs are of length 2, we only add dp[j][d] (not the new pair) to our answer, because these represent extensions to sequences of length at least 2 (thus at least 3 after extension).
5. Final Sum: The sum of all such extensions over all indices and differences gives the total number of arithmetic subsequence slices.

We use hash maps to efficiently store and retrieve the counts for each possible difference, which can be very large or negative.

Example Walkthrough

Consider nums = [2, 4, 6, 8, 10].

1. For each index i, we look at all previous indices j:
   • At i = 1 (nums[1] = 4): Only one pair (2, 4) with difference 2. dp[1][2] = 1.
   • At i = 2 (nums[2] = 6): Pairs are (2, 6) (diff 4), (4, 6) (diff 2). dp[2][4] = 1, dp[2][2] = 2 (one new, one extended from dp[1][2]).
   • At i = 3 (nums[3] = 8): Check (2, 8) (diff 6), (4, 8) (diff 4), (6, 8) (diff 2). Update counts accordingly, extending previous subsequences.
   • Continue similarly for i = 4.
2. At the end, count all extensions (not the new pairs) to get the total number of arithmetic subsequence slices of length at least 3.
3. For this example, the answer is 7, corresponding to all valid arithmetic subsequences like [2,4,6], [4,6,8], [2,4,6,8], [2,6,10], etc.

Time and Space Complexity

• Brute-Force: Generating all subsequences is O(2^n) time and space, which is infeasible for large n.
• Optimized DP Approach:
  • For each pair (i, j), we do O(1) work, and there are O(n^2) such pairs.
  • Each dp[i] hash map may store up to O(n) different differences in the worst case, so space is O(n^2).

  Thus, both time and space complexity are O(n^2).

Summary

The problem of counting arithmetic subsequence slices can be solved efficiently using dynamic programming with hash maps. By focusing on pairs and extending existing subsequences, we avoid exponential time. The key insight is to track, for each index and difference, the number of arithmetic subsequences ending there, and to only count those of length at least 3 towards the answer. This approach is both elegant and efficient, making it feasible for large arrays.