446. Arithmetic Slices II - Explanation

1. Brute Force

Intuition

An arithmetic subsequence has at least 3 elements with a constant difference between consecutive terms. We can try all possible subsequences using recursion, tracking the last two elements to determine the required difference. Once we pick two elements, any future element must continue the same difference.

We use memoization to avoid recomputing the same states. The state includes the current index, the previous index, the difference, and whether we have at least 3 elements.

Algorithm

Use recursion with memoization. The state is (i, j, diff, flag) where i is the current index, j is the last picked index, diff is the arithmetic difference, and flag indicates if we have 3+ elements.
At each index, we can either skip it or include it if it continues the arithmetic sequence.
If we have not picked two elements yet, the difference is undefined. Once two elements are picked, the difference is fixed.
When a third element matches the difference, set flag to 1.
Return the total count of valid subsequences.

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0

        INF = float('inf')
        dp = {}

        def dfs(i, j, diff, flag):
            if i == n:
                return flag
            if (i, j, diff, flag) in dp:
                return dp[(i, j, diff, flag)]

            res = dfs(i + 1, j, diff, flag)
            if j == -1:
                res += dfs(i + 1, i, INF, flag)
            else:
                if diff == INF:
                    res += dfs(i + 1, i, nums[i] - nums[j], flag)
                elif diff == nums[i] - nums[j]:
                    res += dfs(i + 1, i, diff, 1)

            dp[(i, j, diff, flag)] = res
            return res

        return dfs(0, -1, INF, 0)

Time & Space Complexity

Time complexity: $O(n ^ 3)$
Space complexity: $O(n ^ 3)$

2. Dynamic Programming (Bottom-Up)

Intuition

Instead of recursion, we can build the solution iteratively. For each pair of indices (i, j) where j < i, we compute the difference and count how many arithmetic subsequences end at index i with that difference.

The key insight is that dp[i][diff] stores the count of subsequences (of length 2 or more) ending at index i with the given difference. When we extend a subsequence from j to i, we add dp[j][diff] to the result because those represent valid 3+ element subsequences.

Algorithm

Create an array of hash maps. dp[i] maps each difference to the count of subsequences ending at i.
For each pair (j, i) where j < i, compute diff = nums[i] - nums[j].
Add dp[j][diff] to the result (these become valid 3+ element subsequences).
Update dp[i][diff] by adding 1 + dp[j][diff] (the pair plus any extensions).
Return the total count.

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

        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                dp[i][diff] += 1 + dp[j][diff]
                res += dp[j][diff]

        return res

Time & Space Complexity

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

3. Dynamic Programming (Optimization) - I

Intuition

The standard DP approach stores counts for all differences at each index. However, we only need to track a difference if it could potentially extend further. If nums[i] + diff does not exist in the array, there is no point storing that state since no future element can continue the sequence.

By checking if the next element in the sequence exists before storing, we reduce unnecessary hash map entries and improve practical performance.

Algorithm

Store all elements in a set for O(1) lookup.
Create an array of hash maps for DP.
For each pair (j, i), compute the difference.
Only update dp[i][diff] if nums[i] + diff exists in the set (meaning the sequence could continue).
Always add dp[j][diff] to the result regardless of whether we update dp[i].
Return the total count.

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

        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]
                cnt = dp[j].get(diff, 0)
                if nums[i] + diff in s:
                    dp[i][diff] += cnt + 1
                res += cnt

        return res

Time & Space Complexity

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

4. Dynamic Programming (Optimization) - II

Intuition

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.

Algorithm

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

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

Time & Space Complexity

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

Common Pitfalls

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.

# Wrong in languages with fixed-size integers:
int diff = nums[i] - nums[j];  # Can overflow in Java/C++

# Correct: use long
long diff = (long)nums[i] - nums[j];

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.

# Wrong: adding 1 for every pair
res += dp[j][diff] + 1  # Counts pairs, not just 3+ length

# Correct: only count extensions of existing subsequences
res += dp[j][diff]  # Only count when extending to 3+ elements
dp[i][diff] += dp[j][diff] + 1  # Store for future extensions

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.

# Wrong: j as outer loop
for j in range(n):
    for i in range(j + 1, n):
        diff = nums[i] - nums[j]
        res += dp[j][diff]  # dp[j] not fully populated 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.

# Example: nums = [2, 2, 3, 4]
# Both index 0 and 1 have value 2
# Pattern [2,3,4] can start from either index 0 or 1

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.

# Wrong in Java: NullPointerException
int count = dp[j].get(diff);  # Null if key doesn't exist

# Correct: use getOrDefault
int count = dp[j].getOrDefault(diff, 0);