Watch 10 video solutions for Arithmetic Slices II - Subsequence, a hard level problem involving Array, Dynamic Programming. This walkthrough by codestorywithMIK has 23,582 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text 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.
[1, 3, 5, 7, 9], [7, 7, 7, 7], and [3, -1, -5, -9] are arithmetic sequences.[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.
[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 - 1Problem 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 | 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 |