Arithmetic Slices II - Subsequence - Solution & Explanation
Problem Statement
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-231 <= nums[i] <= 231 - 1
Approach Overview
Problem Overview: Given an integer array, count the number of arithmetic subsequences of length ≥ 3. A subsequence is arithmetic if the difference between consecutive elements stays constant. The challenge is that subsequences are not required to be contiguous, which dramatically increases the number of combinations.
Approach 1: Brute Force Enumeration (O(n^3) time, O(1) space)
Generate all possible subsequences of length at least three and check whether the difference between consecutive elements is constant. One way is to fix two starting indices i and j, compute the difference, then scan forward to extend the subsequence whenever the same difference appears. Another variant recursively generates all subsequences and validates them. This approach quickly becomes infeasible because the number of subsequences grows exponentially. It mainly helps build intuition about how arithmetic differences propagate through subsequences.
Approach 2: Dynamic Programming with HashMap (O(n^2) time, O(n^2) space)
Track arithmetic subsequences ending at each index using dynamic programming. Maintain an array dp where dp[i] is a hash map storing difference → count of subsequences ending at index i with that difference. For every pair of indices j < i, compute diff = nums[i] - nums[j]. If dp[j] already has subsequences with this difference, extend them by adding nums[i]. Each extension forms a longer arithmetic subsequence. Update dp[i][diff] and accumulate counts into the final result. This avoids recomputing subsequences and efficiently builds longer ones from shorter ones.
The key insight: every arithmetic subsequence of length ≥3 is created by extending a length ≥2 subsequence with the same difference. Hash maps allow constant‑time lookup of how many subsequences with that difference already exist. The algorithm iterates over all pairs of indices once, making it scalable for larger arrays.
Recommended for interviews: The Dynamic Programming with HashMap approach is the expected solution. It demonstrates understanding of subsequence DP and efficient state tracking. Interviewers may start with brute force discussion to confirm reasoning, but the optimized DP solution shows strong mastery of Array processing and Dynamic Programming techniques.
Approach 1: 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.
This C solution involves using a 2D array `dp` where `dp[i][d]` represents the number of arithmetic subsequences ending at index `i` with common difference `d`. We iterate through pairs `(i, j)` where `j < i` and calculate the difference `d`. For each pair, we update the `dp` array and accumulate the answer in `res` by adding the count of subsequences ending at `j` with difference `d`.
Complexity
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).
Approach 2: 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.
This C program generates all combinations as potential subsequences and checks whether each subsequence is arithmetic by comparing adjacent differences. Due to its combinatorial nature, this approach is inefficient for large inputs but helps in understanding smaller cases.
Complexity
Time Complexity: O(n * 2^n) for combinations, where n is length of `nums`.
Space Complexity: O(n) given additional space for combinations.
Approach 3: Default Approach
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with HashMap | Time Complexity: O(n^2), where n is the length of the input array. |
| Brute Force Approach (Inefficient for Larger Inputs) | Time Complexity: O(n * 2^n) for combinations, where n is length of `nums`. |
| Default Approach | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(n^3) | O(1) | Useful only for understanding the problem or very small arrays |
| Dynamic Programming with HashMap | O(n^2) | O(n^2) | General optimal solution for counting arithmetic subsequences efficiently |
Video Solution
Arithmetic Slices II - Subsequence | Hard Made Easy | Intuition | Leetcode 446 • codestorywithMIK • 26,059 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Arithmetic Slices II - Subsequence easy or hard?
Arithmetic Slices II - Subsequence Python/Java solution
How to solve Arithmetic Slices II - Subsequence in O(n)?
What is the best approach for Arithmetic Slices II - Subsequence?
Is Arithmetic Slices II - Subsequence asked at Google/Amazon/Meta?
What data structure is used in Arithmetic Slices II - Subsequence?
What is the time complexity of Arithmetic Slices II - Subsequence?
Ready to solve this problem?
Practice Arithmetic Slices II - Subsequence with our built-in code editor and test cases.
Practice on FleetCode