LeetCode 446 - Arithmetic Slices II - Subsequence

LeetCode Problem 446

Difficulty: 🔴 Hard
Topics: Array, Dynamic Programming

Solution

Problem Understanding

The problem asks us to count how many arithmetic subsequences exist inside a given integer array nums.

An arithmetic sequence is a sequence where the difference between consecutive elements is constant. The sequence must contain at least three elements. Unlike subarrays, subsequences do not need to be contiguous. We are allowed to skip elements as long as the relative ordering remains unchanged.

For example, in the array [2,4,6,8,10], the subsequence [2,6,10] is valid because the consecutive differences are all 4, even though the elements are not adjacent in the original array.

The input is an integer array with length up to 1000. The values themselves can be as small as -2^31 and as large as 2^31 - 1. These constraints are important because:

• A brute-force subsequence enumeration is impossible, since an array of size 1000 has 2^1000 subsequences.
• Differences between two numbers may overflow a 32-bit integer, so we must use a wider integer type when computing differences.
• The result itself is guaranteed to fit inside a 32-bit integer.

The output should be the total number of arithmetic subsequences of length at least 3.

A critical detail is that subsequences of length 2 are not counted directly. However, they are extremely important during dynamic programming because longer arithmetic subsequences are built by extending shorter ones.

Several edge cases can easily break naive implementations:

• Arrays with all equal numbers produce many overlapping arithmetic subsequences.
• Negative differences must be handled correctly.
• Large integer values can cause overflow when computing differences.
• Arrays shorter than length 3 always produce 0.
• Duplicate values create many distinct subsequences even when the numeric values look identical.

Approaches

Brute Force

A brute-force solution would generate every possible subsequence of the array, then check whether each subsequence is arithmetic.

To verify whether a subsequence is arithmetic, we compute the difference between adjacent elements and ensure all differences are identical. Any subsequence of length at least 3 satisfying this condition contributes to the answer.

This approach is correct because it explicitly examines every possible subsequence. However, it is computationally infeasible.

An array of length n has 2^n subsequences. With n = 1000, this becomes astronomically large. Even checking each subsequence efficiently would still be hopelessly slow.

Optimal Dynamic Programming Approach

The key observation is that arithmetic subsequences are defined entirely by:

• Their ending position
• Their common difference

This suggests a dynamic programming formulation.

Suppose we want to know how many arithmetic subsequences end at index i with common difference d.

If we look at some earlier index j < i, and:

nums[i] - nums[j] = d

then every arithmetic subsequence ending at j with difference d can be extended by nums[i].

Additionally, the pair (nums[j], nums[i]) itself forms a new subsequence of length 2, which may later grow into a valid arithmetic subsequence.

This leads to a DP structure where:

• dp[i][d] stores the number of arithmetic subsequences of length at least 2 ending at index i with difference d
• When extending an existing subsequence, we add to the final answer because the resulting subsequence now has length at least 3

This transforms the problem from exponential complexity into quadratic complexity.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n)	O(n)	Enumerates every subsequence and checks arithmetic validity
Optimal Dynamic Programming	O(n^2)	O(n^2)	Tracks subsequence counts by ending index and difference

Algorithm Walkthrough

1. Create a DP array where each position contains a hash map.

Each dp[i] is a map:

difference -> count

The value represents how many arithmetic subsequences of length at least 2 end at index i with that difference. 2. Initialize the final answer to 0.

The answer only counts subsequences of length at least 3. 3. Iterate through every pair of indices (j, i) where j < i.

This pair represents a potential extension of arithmetic subsequences. 4. Compute the difference:

diff = nums[i] - nums[j]

We use a 64-bit integer because the subtraction may overflow a 32-bit integer. 5. Determine how many subsequences already end at j with this difference.

previous_count = dp[j][diff]

These are all arithmetic subsequences that can be extended using nums[i]. 6. Add previous_count to the answer.

Every extension increases the subsequence length by one, so each becomes a valid arithmetic subsequence of length at least 3. 7. Update dp[i][diff].

We add:

• previous_count, representing all extended subsequences
• 1, representing the new length-2 subsequence (nums[j], nums[i])

So:

dp[i][diff] += previous_count + 1

8. Continue until all pairs have been processed.
9. Return the accumulated answer.

Why it works

The invariant is that dp[i][diff] always stores the number of arithmetic subsequences of length at least 2 ending at index i with common difference diff.

Whenever we process a pair (j, i):

• Every existing subsequence ending at j with difference diff can be safely extended to i
• Extending preserves the arithmetic property because the difference remains unchanged
• Every such extension creates a valid arithmetic subsequence of length at least 3

Since every arithmetic subsequence has a unique final index and difference, every valid subsequence is counted exactly once.

Python Solution

from collections import defaultdict
from typing import List

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        n = len(nums)

        # dp[i][diff] = number of arithmetic subsequences
        # of length >= 2 ending at index i with difference diff
        dp = [defaultdict(int) for _ in range(n)]

        total_slices = 0

        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]

                previous_count = dp[j][diff]

                # Extend all previous subsequences
                total_slices += previous_count

                # Add:
                # 1 for the new pair (nums[j], nums[i])
                # previous_count for all extended subsequences
                dp[i][diff] += previous_count + 1

        return total_slices

The implementation closely follows the dynamic programming strategy described earlier.

We first create a list of hash maps called dp. Each map tracks how many arithmetic subsequences end at a particular index for each difference value.

The outer loop selects the current ending index i. The inner loop considers every earlier index j, forming a pair (j, i).

For each pair, we compute the difference:

diff = nums[i] - nums[j]

We then look up how many arithmetic subsequences already ended at j using this same difference.

previous_count = dp[j][diff]

These subsequences can all be extended by appending nums[i].

Those extensions immediately contribute to the final answer because they now have length at least 3.

Finally, we update:

dp[i][diff] += previous_count + 1

The +1 accounts for the new subsequence of length 2 formed by (nums[j], nums[i]).

Go Solution

func numberOfArithmeticSlices(nums []int) int {
	n := len(nums)

	// dp[i][diff] = number of arithmetic subsequences
	// of length >= 2 ending at index i with difference diff
	dp := make([]map[int64]int, n)

	for i := 0; i < n; i++ {
		dp[i] = make(map[int64]int)
	}

	totalSlices := 0

	for i := 0; i < n; i++ {
		for j := 0; j < i; j++ {
			diff := int64(nums[i]) - int64(nums[j])

			previousCount := dp[j][diff]

			// Extend previous subsequences
			totalSlices += previousCount

			// Add new pair and extended subsequences
			dp[i][diff] += previousCount + 1
		}
	}

	return totalSlices
}

The Go implementation mirrors the Python solution almost exactly.

The main difference is that Go requires explicit map initialization for every dp[i].

Another important difference is integer handling. Since subtracting two 32-bit integers may overflow, the difference is stored as int64:

diff := int64(nums[i]) - int64(nums[j])

Go maps return the zero value for missing keys automatically, which simplifies the lookup logic.

Worked Examples

Example 1

Input:

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

We track:

dp[i][diff]

and the running answer.

i	j	nums[i]	nums[j]	diff	previous_count	New dp[i][diff]	total
1	0	4	2	2	0	1	0
2	0	6	2	4	0	1	0
2	1	6	4	2	1	2	1
3	0	8	2	6	0	1	1
3	1	8	4	4	0	1	1
3	2	8	6	2	2	3	3
4	0	10	2	8	0	1	3
4	1	10	4	6	0	1	3
4	2	10	6	4	1	2	4
4	3	10	8	2	3	4	7

Final answer:

7

The counted subsequences are:

[2,4,6]
[4,6,8]
[6,8,10]
[2,4,6,8]
[4,6,8,10]
[2,4,6,8,10]
[2,6,10]

Example 2

Input:

nums = [7,7,7,7,7]

Every difference is 0.

i	j	diff	previous_count	dp[i][0]	total
1	0	0	0	1	0
2	0	0	0	1	0
2	1	0	1	3	1
3	0	0	0	1	1
3	1	0	1	3	2
3	2	0	3	7	5
4	0	0	0	1	5
4	1	0	1	3	6
4	2	0	3	7	9
4	3	0	7	15	16

Final answer:

16

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n^2)	Every pair of indices (j, i) is processed once
Space	O(n^2)	In the worst case, each index stores many distinct differences

The nested loops examine all pairs of indices, producing quadratic time complexity.

The DP structure may also grow quadratically in the worst case because each pair of indices can introduce a distinct difference value.

Test Cases

from typing import List

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        from collections import defaultdict

        n = len(nums)
        dp = [defaultdict(int) for _ in range(n)]

        total = 0

        for i in range(n):
            for j in range(i):
                diff = nums[i] - nums[j]

                prev = dp[j][diff]

                total += prev
                dp[i][diff] += prev + 1

        return total

sol = Solution()

assert sol.numberOfArithmeticSlices([2,4,6,8,10]) == 7
# Standard increasing arithmetic progression

assert sol.numberOfArithmeticSlices([7,7,7,7,7]) == 16
# All elements equal

assert sol.numberOfArithmeticSlices([1,2]) == 0
# Array too short

assert sol.numberOfArithmeticSlices([1,2,3]) == 1
# Single arithmetic subsequence

assert sol.numberOfArithmeticSlices([1,3,5,7,9]) == 7
# Multiple overlapping arithmetic subsequences

assert sol.numberOfArithmeticSlices([1,1,1]) == 1
# Minimal repeated-values case

assert sol.numberOfArithmeticSlices([1,1,1,1]) == 5
# Many duplicate-based subsequences

assert sol.numberOfArithmeticSlices([3,-1,-5,-9]) == 3
# Negative difference handling

assert sol.numberOfArithmeticSlices([1,5,9,13,17]) == 7
# Larger arithmetic progression

assert sol.numberOfArithmeticSlices([1,2,4,8,16]) == 0
# No valid arithmetic subsequences

assert sol.numberOfArithmeticSlices([0,2000000000,-294967296]) == 0
# Large values testing overflow safety

Test	Why
[2,4,6,8,10]	Standard example with overlapping subsequences
[7,7,7,7,7]	Verifies handling of repeated values
[1,2]	Confirms arrays shorter than 3 return 0
[1,2,3]	Smallest valid arithmetic subsequence
[1,3,5,7,9]	Multiple valid subsequences with same difference
[1,1,1]	Duplicate handling for minimal valid size
[1,1,1,1]	Stress test for repeated values
[3,-1,-5,-9]	Negative common differences
[1,5,9,13,17]	Longer arithmetic progression
[1,2,4,8,16]	No arithmetic subsequences
[0,2000000000,-294967296]	Overflow safety validation

Edge Cases

Arrays Shorter Than Three Elements

An arithmetic subsequence must contain at least three elements. Arrays of length 0, 1, or 2 should always return 0.

This is easy to mishandle if the implementation accidentally counts pairs as valid arithmetic subsequences. The DP formulation avoids this bug because pairs are only stored as intermediate building blocks and are never directly added to the answer.

All Elements Equal

An array like:

[7,7,7,7,7]

creates a massive number of valid arithmetic subsequences because every subsequence has common difference 0.

This case stresses whether the implementation correctly accumulates counts rather than overwriting them. Using:

dp[i][diff] += previous_count + 1

ensures all overlapping subsequences are preserved.

Integer Overflow in Difference Calculation

The constraints allow values near the 32-bit integer limits.

For example:

nums[i] = 2147483647
nums[j] = -2147483648

Their difference exceeds the range of a signed 32-bit integer.

If the implementation stores differences in 32-bit integers, incorrect collisions may occur inside the hash map, producing invalid counts.

The solution avoids this problem by using Python's arbitrary precision integers and int64 in Go.