Arithmetic Slices II - Subsequence

How it works

Instead of using a hash map keyed by difference, we can use a 2D DP array where dp[i][j] represents the count of arithmetic subsequences ending at indices i and j. To extend a subsequence ending at j, we need to find an earlier index k such that nums[j] - nums[k] = nums[i] - nums[j].

We precompute the indices of each value in a map. For a pair (j, i), we calculate the required previous value as 2 * nums[j] - nums[i] and look up all indices where this value appears.

Steps

1. Build a map from each value to the list of indices where it appears.
2. Create a 2D DP array where dp[i][j] counts subsequences ending at positions j and i.
3. For each pair (j, i) where j < i, compute prev = 2 * nums[j] - nums[i].
4. Look up all indices k < j where nums[k] = prev and add dp[j][k] + 1 to dp[i][j].
5. Accumulate dp[i][j] into the result.
6. Return the total count.

Complexity

• Time complexity: O(n ^ 2)
• Space complexity: O(n ^ 2)

Things to watch for

Integer Overflow When Computing Differences

The difference between two elements can exceed the range of a 32-bit integer (e.g., INT_MAX - INT_MIN). You must use a 64-bit integer type for the difference to avoid overflow and incorrect hash map lookups.

Counting Pairs Instead of Subsequences of Length 3+

The DP stores counts of subsequences of length 2 or more ending at each index. You only add to the result when extending an existing subsequence (making it length 3+), not when creating a new pair.

Using the Wrong Index Order in Nested Loops

The outer loop must be the current index i and inner loop must iterate through all previous indices j < i. Reversing this order means you're trying to access DP values that haven't been computed yet.

Forgetting to Handle Duplicate Values

When the array contains duplicate values, multiple indices can have the same value. The DP must correctly accumulate counts from all valid previous indices, not just the first occurrence of a value.

Not Initializing DP Entries Before Access

In some languages, accessing a missing key in a hash map returns null or throws an error. Ensure you handle missing keys by using default values or checking existence before access.

from typing import List
from collections import defaultdict

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        res = 0
        mpIdx = defaultdict(list)
        n = len(nums)
        dp = [[0] * n for _ in range(n)]

        for i in range(n):
            mpIdx[nums[i]].append(i)

        for i in range(n):
            for j in range(i):
                prev = 2 * nums[j] - nums[i]
                if prev in mpIdx:
                    for k in mpIdx[prev]:
                        if k >= j:
                            break
                        dp[i][j] += dp[j][k] + 1
                res += dp[i][j]

        return res

class Solution {
public:
    int numberOfArithmeticSlices(vector<int>& nums) {
        int res = 0;
        unordered_map<int, vector<int>> mpIdx;
        int n = nums.size();
        vector<vector<int>> dp(n, vector<int>(n, 0));

        for (int i = 0; i < n; i++) {
            mpIdx[nums[i]].push_back(i);
        }

        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                long prev = 2L * nums[j] - nums[i];
                if (prev < INT_MIN || prev > INT_MAX) continue;

                if (mpIdx.count(prev)) {
                    for (int k : mpIdx[prev]) {
                        if (k >= j) break;
                        dp[i][j] += dp[j][k] + 1;
                    }
                }
                res += dp[i][j];
            }
        }

        return res;
    }
};