#446

Hard

auto_awesomeState transition dynamic programming

LeetCode Problem Workspace

Arithmetic Slices II - Subsequence

Count all arithmetic subsequences in an array using dynamic programming with precise state transitions for correctness.

Problem Statement

Given an integer array nums, return the total number of arithmetic subsequences present in nums. A subsequence is defined as a sequence that can be derived from nums by deleting zero or more elements without changing the order of the remaining elements.

A sequence is arithmetic if it contains at least three numbers and the difference between consecutive elements is consistent. For example, for nums = [2,4,6,8,10], all subsequences like [2,4,6] or [2,4,6,8,10] are considered arithmetic.

Examples

Example 1

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

Output: 7

All arithmetic subsequence slices 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]

Output: 16

Any subsequence of this array is arithmetic.

Constraints

1 <= nums.length <= 1000
-231 <= nums[i] <= 231 - 1

Solution Approach

Track differences with DP maps

Use an array of hash maps, where each map at index i counts subsequences ending at nums[i] with a given difference. Iterate through each pair (i, j), compute the difference, and update counts based on prior sequences to extend arithmetic subsequences.

Handle subsequences of length >= 3

While updating counts, distinguish between new subsequences of length 2 and extensions of existing ones. Only sequences extended from length 2 or more contribute to the final count, ensuring correctness for the arithmetic requirement.

Prevent integer overflow and duplicates

Since differences can be large, cast to long or use proper integer handling. Merge counts carefully to avoid double-counting, especially with duplicate numbers in the array, which are common in test cases.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n^2) due to examining all pairs for differences. Space complexity is O(n * m) where m is the average number of distinct differences tracked per index. Efficient hash map usage prevents unnecessary overhead.

What Interviewers Usually Probe

Expect candidates to mention dynamic programming with difference tracking immediately.
Look for recognition that subsequences of length 2 are building blocks for length >= 3 sequences.
Candidates should handle large integers and duplicates to avoid incorrect counting.

Common Pitfalls or Variants

Common pitfalls

Counting all subsequences including those shorter than 3, inflating the result.
Overwriting counts instead of accumulating, leading to missed sequences.
Failing to handle duplicate elements properly, causing double-counting or omission.

Follow-up variants

Compute the number of arithmetic subsequences with a fixed target difference.
Find the longest arithmetic subsequence instead of total count.
Count arithmetic subsequences modulo a large prime to prevent overflow.

FAQ

What is the main strategy to solve Arithmetic Slices II - Subsequence efficiently?

Use state transition dynamic programming with hash maps to track differences and extend subsequences, counting only those with length >= 3.

How do I handle duplicates in nums when counting subsequences?

Accumulate counts carefully in the DP maps to avoid double-counting, treating each index separately even if values repeat.

Does the difference need to be positive for arithmetic subsequences?

No, differences can be negative or zero. The key requirement is consistency between consecutive elements.

Can subsequences be non-contiguous?

Yes, subsequences are formed by removing zero or more elements without reordering, so they can skip elements in nums.

What is a common failure mode in interviews for this problem?

Forgetting to exclude subsequences shorter than 3 or mishandling duplicates is a frequent mistake that leads to wrong counts.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

class Solution:
    def numberOfArithmeticSlices(self, nums: List[int]) -> int:
        f = [defaultdict(int) for _ in nums]
        ans = 0
        for i, x in enumerate(nums):
            for j, y in enumerate(nums[:i]):
                d = x - y
                ans += f[j][d]
                f[i][d] += f[j][d] + 1
        return ans

Continue Practicing

#435 non overlapping intervals #472 concatenated words #473 matchsticks to square