#446 Arithmetic Slices II - Subsequence - Solution

Given an integer array nums, return the number of all the arithmetic subsequences of nums.

A sequence of numbers is called arithmetic if it consists of at least three elements and if the difference between any two consecutive elements is the same.

For example, [1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.
For example, [1, 1, 2, 5, 7] is not an arithmetic sequence.

A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array.

For example, [2,5,10] is a subsequence of [1,2,1,2,4,1,5,10].

The test cases are generated so that the answer fits in 32-bit integer.

Example 1:

Input: nums = [2,4,6,8,10]
Output: 7
Explanation: 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
Explanation: Any subsequence of this array is arithmetic.

Constraints:

1 <= nums.length <= 1000
-2³¹ <= nums[i] <= 2³¹ - 1

#446 Arithmetic Slices II - Subsequence asks you to count the number of arithmetic subsequences of length ≥ 3 in an array. A brute-force approach would try all subsequences, but this quickly becomes infeasible. Instead, an efficient solution relies on dynamic programming with hash maps.

The key idea is to track arithmetic differences. For every index i, maintain a map where the key is the common difference and the value is the number of subsequences ending at i with that difference. While iterating through pairs (j, i) with j < i, compute the difference diff = nums[i] - nums[j]. Extend any subsequences ending at j with the same difference and update the count at i. Only subsequences of length ≥ 3 contribute to the final answer.

This dynamic programming strategy avoids recomputation and systematically builds longer sequences from shorter ones. The algorithm processes all pairs once, leading to O(n²) time complexity, while storing difference counts per index results in approximately O(n²) space in the worst case.

Approach	Time Complexity	Space Complexity
Dynamic Programming with Hash Maps	O(n^2)	O(n^2)

Solutions (12)

Dynamic Programming with HashMap

This approach uses dynamic programming and hashmaps to calculate arithmetic subsequences efficiently. For each index, we maintain a hashmap that tracks the count of different differences (arithmetic differences) and the number of subsequences that end with that difference at the given index. This allows us to build potential subsequences as we iterate over the array.

Time Complexity: O(n^2), where n is the length of the input array.
Space Complexity: O(n * m), where m is the number of possible differences (limited by the constraint of 31-bit integer).

C C++Java Python C#JavaScript

1from collections import defaultdict
2
3def numberOfArithmeticSlices(nums):
4    total, n = 0, len(nums)
5    dp = [defaultdict(int

Explanation

This Python solution uses `defaultdict` to automatically handle key presence in the dictionary for differences. The outer loop iterates over `i` and the inner loop computes over all previous indices `j`, forming differences and updating the counts.

Brute Force Approach (Inefficient for Larger Inputs)

This approach considers all possible subsequences (using combinations) and checks if each subsequence is arithmetic. Although not efficient, it can be used to demonstrate the logic on small arrays to understand the problem better.

Time Complexity: O(n * 2^n) for combinations, where n is length of `nums`.
Space Complexity: O(n) given additional space for combinations.

C C++Java Python C#JavaScript

1using System.Collections.Generic;

class ArithmeticSlicesBrute {

    private bool IsArithmetic(List<int> seq) {
        if (seq.Count < 3) return false;
        int diff = seq[1] - seq[0];
        for (int i = 2; i < seq.Count; i++) {
            if (seq[i] - seq[i - 1] != diff)
                return false;
        }
        return true;
    }

    private void GenerateSubsequences(int[] nums, List<int> curr, int start, ref int total) {
        if (curr.Count >= 3 && IsArithmetic(curr)) {
            total++;
        }
        for (int i = start; i < nums.Length; i++) {
            curr.Add(nums[i]);
            GenerateSubsequences(nums, curr, i + 1, ref total);
            curr.RemoveAt(curr.Count - 1);
        }
    }

    public int NumberOfArithmeticSlices(int[] nums) {
        List<int> curr = new List<int>();
        int total = 0;
        GenerateSubsequences(nums, curr, 0, ref total);
        return total;
    }

    static void Main() {
        int[] nums = {2, 4, 6, 8, 10};
        ArithmeticSlicesBrute asb = new ArithmeticSlicesBrute();
        Console.WriteLine(asb.NumberOfArithmeticSlices(nums));
    }
}