Arithmetic Slices II - Subsequence — Problem & Solution
Arithmetic Slices II - Subsequence solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.
Arithmetic Slices II - Subsequence is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon, Google and Microsoft interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Dynamic Programming
- Asked at: Amazon, Google, Microsoft
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A sequence is arithmetic when it has at least three elements and every two neighbours differ by the same amount. [4,4,4], [7,10,13] and [3,-1,-5,-9] are arithmetic; [1,2,4] and [5,8] are not.
Given an integer array nums, count its arithmetic subsequences. A subsequence keeps the original order but may skip elements. Two subsequences are different when they use different sets of indices, even if they hold the same values.
The answer is guaranteed to fit in a 32-bit signed integer.
Example 1
Input: nums = [2,4,6,8,10]
Output: 7
Explanation: `[2,4,6]`, `[4,6,8]`, `[6,8,10]`, `[2,4,6,8]`, `[4,6,8,10]`, `[2,4,6,8,10]` and `[2,6,10]`.
Example 2
Input: nums = [5,5,5,5]
Output: 5
Explanation: Any three of the four positions (4 ways) and all four together.
Example 3
Input: nums = [9,6,3,7,0]
Output: 3
Explanation: `[9,6,3]`, `[6,3,0]` and `[9,6,3,0]` — the `7` never fits.
Constraints
1 <= nums.length <= 1000-2^31 <= nums[i] <= 2^31 - 1the answer fits in a 32-bit signed integer
Hints for Arithmetic Slices II - Subsequence
Hint 1
Build subsequences left to right: an arithmetic subsequence ending at index
iwith common differencedextends one that ends at somej < iwith the samed.Hint 2
Also count the 'weak' ones of length 2. Every pair
(j, i)starts one, and a real answer is exactly a weak subsequence that gets extended at least once.Hint 3
For each index keep a map from difference to the number of weak subsequences ending there. For every
j < iwithd = nums[i] - nums[j]: addcount[j][d]to the answer, then addcount[j][d] + 1tocount[i][d].
How to solve Arithmetic Slices II - Subsequence
Track weak arithmetic subsequences — length two or more. Length-2 ones are easy to start (every pair is one), and a length-≥3 one is precisely a weak subsequence ending at j with difference d, extended by an element nums[i] with nums[i] - nums[j] = d.
Approach
- Give every index
ia hash mapcount[i]from difference to the number of weak subsequences ending atiwith that difference. - For each
iand eachj < i, letd = nums[i] - nums[j](in 64 bits). - Every weak subsequence counted in
count[j][d]extends to a subsequence of length ≥ 3 ending ati: addcount[j][d]to the answer. - Record the new weak subsequences ending at
i:count[i][d] += count[j][d] + 1(the extensions plus the pair(j, i)itself). - Return the accumulated answer.
Why it works
Each arithmetic subsequence is identified by its last two indices (j, i) and its prefix ending at j. When the pair (j, i) is processed, count[j][d] already holds every weak subsequence ending at j with difference d (all of them end at indices below i), so each arithmetic subsequence is added to the answer exactly once — at the moment its last element is appended — and length-2 pairs never reach the answer because they are added to count[i] only.
Complexity
- Time —
O(n^2) - Space —
O(n^2)
Pitfalls
- Differences of values near ±2^31 overflow 32 bits — compute
din 64-bit arithmetic. - Add
count[j][d]to the answer, notcount[j][d] + 1: the bare pair has length 2. - Equal values are fine:
d = 0is a valid difference, and duplicates are different subsequences because their indices differ.
Reference solution
Python
from typing import List
def numberOfArithmeticSlices(nums: List[int]) -> int:
n = len(nums)
count = [dict() for _ in range(n)]
total = 0
for i in range(n):
here = count[i]
for j in range(i):
d = nums[i] - nums[j]
c = count[j].get(d, 0)
total += c
here[d] = here.get(d, 0) + c + 1
return totalJava
public static int numberOfArithmeticSlices(int[] nums) {
int n = nums.length;
long total = 0;
List<Map<Long, Long>> count = new ArrayList<>();
for (int i = 0; i < n; i++) {
Map<Long, Long> here = new HashMap<>();
count.add(here);
for (int j = 0; j < i; j++) {
long d = (long) nums[i] - nums[j];
long c = count.get(j).getOrDefault(d, 0L);
total += c;
here.put(d, here.getOrDefault(d, 0L) + c + 1);
}
}
return (int) total;
}C++
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
long long total = 0;
vector<unordered_map<long long, long long>> count(n);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
long long d = (long long)nums[i] - nums[j];
auto it = count[j].find(d);
long long c = it == count[j].end() ? 0 : it->second;
total += c;
count[i][d] += c + 1;
}
}
return (int)total;
}JavaScript
var numberOfArithmeticSlices = function(nums) {
var n = nums.length, total = 0;
var count = [];
for (var i = 0; i < n; i++) {
var here = new Map();
count.push(here);
for (var j = 0; j < i; j++) {
var d = nums[i] - nums[j];
var c = count[j].get(d) || 0;
total += c;
here.set(d, (here.get(d) || 0) + c + 1);
}
}
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets