Arithmetic Slices II - Subsequence solution and explanation
Google
9 more videos on this problem
Arithmetic Slices II - Subsequence | Hard Made Easy | Intuition | Leetcode 446codestorywithMIK · 29:24 · 26K views
Arithmetic Slices II - Leetcode 446 - PythonNeetCodeIO · 21:19 · 19K views
Arithmetic Slices II Subsequence | Leetcode 446 | Live coding session 🔥🔥🔥Coding Decoded · 19:45 · 4K views
446. Arithmetic Slices II - Subsequence | DPAryan Mittal · 23:49 · 4K views
LeetCode 446. Arithmetic Slices II - SubsequenceHappy Coding · 17:30 · 2K views
Arithmetic Slices II Subsequence | Observation Based Solution ExplainedTanishq Chaudhary · 14:17 · 1K views
Leetcode - Arithmetic Slices II - Subsequence (Python)Timothy H Chang · 8:55 · 1K views
Daily Leetcode #971: Nov 27, 2022 - 446. Arithmetic Slices II - SubsequenceProgramming Live with Larry · 27:11 · 1K views
Daily Leetcode #528: Sep 10, 2021 - 446. Arithmetic Slices II - SubsequenceProgramming Live with Larry · 36:16 · 516 views
446. Arithmetic Slices II - Subsequence | Leetcode Problems | #DSA #CPTejpratap Pandey · 20:03 · 494 views
The problem
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.
from collections import defaultdict
def numberOfArithmeticSlices(nums):
total, n = 0, len(nums)
dp = [defaultdict(int) for _ in range(n)]
for i in range(n):
for j in range(i):
diff = nums[i] - nums[j]
count_at_j = dp[j][diff]
dp[i][diff] += count_at_j + 1
total += count_at_j
return total
# Test
nums = [2, 4, 6, 8, 10]
print(numberOfArithmeticSlices(nums))import java.util.*;
public class ArithmeticSlices {
public int numberOfArithmeticSlices(int[] nums) {
int n = nums.length;
int total = 0;
Map<Long, Integer>[] dp = new Map[n];
for (int i = 0; i < n; i++) {
dp[i] = new HashMap<>();
for (int j = 0; j < i; j++) {
long diff = (long) nums[i] - (long) nums[j];
int count_j = dp[j].getOrDefault(diff, 0);
dp[i].put(diff, dp[i].getOrDefault(diff, 0) + count_j + 1);
total += count_j;
}
}
return total;
}
public static void main(String[] args) {
ArithmeticSlices as = new ArithmeticSlices();
int[] nums = {2, 4, 6, 8, 10};
System.out.println(as.numberOfArithmeticSlices(nums));
}
}#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;
int numberOfArithmeticSlices(vector<int>& nums) {
int n = nums.size();
int total = 0;
vector<unordered_map<long, int>> dp(n);
for (int i = 0; i < n; ++i) {
for (int j = 0; j < i; ++j) {
long diff = (long)nums[i] - (long)nums[j];
int count_at_j = dp[j][diff];
dp[i][diff] += count_at_j + 1;
total += count_at_j;
}
}
return total;
}
int main() {
vector<int> nums = {2, 4, 6, 8, 10};
cout << numberOfArithmeticSlices(nums) << endl;
return 0;
}function numberOfArithmeticSlices(nums) {
const n = nums.length;
let total = 0;
const dp = Array(n).fill(0).map(() => new Map());
for (let i = 0; i < n; i++) {
for (let j = 0; j < i; j++) {
const diff = nums[i] - nums[j];
const countAtJ = dp[j].get(diff) || 0;
dp[i].set(diff, (dp[i].get(diff) || 0) + countAtJ + 1);
total += countAtJ;
}
}
return total;
}
// Test
console.log(numberOfArithmeticSlices([2, 4, 6, 8, 10]));#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MAX_DIFF 20000
#define OFFSET 10000
int numberOfArithmeticSlices(int* nums, int numsSize) {
int res = 0;
int dp[numsSize][MAX_DIFF] = {0};
for (int i = 1; i < numsSize; i++) {
for (int j = 0; j < i; j++) {
long diff = (long)nums[i] - (long)nums[j] + OFFSET;
int count_at_j = dp[j][diff];
dp[i][diff] += count_at_j + 1;
res += count_at_j;
}
}
return res;
}
int main() {
int nums[] = {2, 4, 6, 8, 10};
int numsSize = sizeof(nums) / sizeof(nums[0]);
int result = numberOfArithmeticSlices(nums, numsSize);
printf("%d\n", result);
return 0;
}using System;
using System.Collections.Generic;
class ArithmeticSlices {
public static int NumberOfArithmeticSlices(int[] nums) {
int total = 0;
int n = nums.Length;
var dp = new Dictionary<long, int>[n];
for (int i = 0; i < n; i++) {
dp[i] = new Dictionary<long, int>();
for (int j = 0; j < i; j++) {
long diff = (long)nums[i] - (long)nums[j];
dp[i].TryGetValue(diff, out int endCount); // Existing count
dp[j].TryGetValue(diff, out int countAtJ);
dp[i][diff] = endCount + countAtJ + 1;
total += countAtJ;
}
}
return total;
}
static void Main() {
int[] nums = {2, 4, 6, 8, 10};
Console.WriteLine(NumberOfArithmeticSlices(nums));
}
}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.
Time Complexity: O(n^2), with n the length of nums.
Space Complexity: O(n * m), with m being the unique differences for indices.
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.
def is_arithmetic(seq):
if len(seq) < 3:
return False
diff = seq[1] - seq[0]
for i in range(2, len(seq)):
if seq[i] - seq[i - 1] != diff:
return False
return True
def generate_subsequences(nums, curr, start, total):
if len(curr) >= 3 and is_arithmetic(curr):
total[0] += 1
for i in range(start, len(nums)):
generate_subsequences(nums, curr + [nums[i]], i + 1, total)
def number_of_arithmetic_slices(nums):
total = [0]
generate_subsequences(nums, [], 0, total)
return total[0]
# Test
nums = [2, 4, 6, 8, 10]
print(number_of_arithmetic_slices(nums))import java.util.*;
class ArithmeticSlicesBrute {
private boolean isArithmetic(List<Integer> seq) {
if (seq.size() < 3) return false;
int diff = seq.get(1) - seq.get(0);
for (int i = 2; i < seq.size(); i++) {
if (seq.get(i) - seq.get(i - 1) != diff)
return false;
}
return true;
}
private void generateSubsequences(int[] nums, List<Integer> curr, int start, int[] total) {
if (curr.size() >= 3 && isArithmetic(curr)) {
total[0]++;
}
for (int i = start; i < nums.length; i++) {
curr.add(nums[i]);
generateSubsequences(nums, curr, i + 1, total);
curr.remove(curr.size() - 1);
}
}
public int numberOfArithmeticSlices(int[] nums) {
List<Integer> curr = new ArrayList<>();
int[] total = new int[1];
generateSubsequences(nums, curr, 0, total);
return total[0];
}
public static void main(String[] args) {
ArithmeticSlicesBrute asb = new ArithmeticSlicesBrute();
int[] nums = {2, 4, 6, 8, 10};
System.out.println(asb.numberOfArithmeticSlices(nums));
}
}#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
bool isArithmetic(vector<int>& seq) {
if (seq.size() < 3) return false;
int diff = seq[1] - seq[0];
for (size_t i = 2; i < seq.size(); i++) {
if (seq[i] - seq[i - 1] != diff)
return false;
}
return true;
}
void generateSubsequences(vector<int>& nums, vector<int>& curr, int start, int& total) {
if (curr.size() >= 3 && isArithmetic(curr)) {
total++;
}
for (size_t i = start; i < nums.size(); i++) {
curr.push_back(nums[i]);
generateSubsequences(nums, curr, i + 1, total);
curr.pop_back();
}
}
int numberOfArithmeticSlices(vector<int>& nums) {
vector<int> curr;
int total = 0;
generateSubsequences(nums, curr, 0, total);
return total;
}
int main() {
vector<int> nums = {2, 4, 6, 8, 10};
cout << numberOfArithmeticSlices(nums) << endl;
return 0;
}function isArithmetic(seq) {
if (seq.length < 3) return false;
const diff = seq[1] - seq[0];
for (let i = 2; i < seq.length; i++) {
if (seq[i] - seq[i - 1] !== diff) return false;
}
return true;
}
function generateSubsequences(nums, curr, start, total) {
if (curr.length >= 3 && isArithmetic(curr)) {
total.push(1);
}
for (let i = start; i < nums.length; i++) {
generateSubsequences(nums, curr.concat(nums[i]), i + 1, total);
}
}
function numberOfArithmeticSlices(nums) {
const total = [];
generateSubsequences(nums, [], 0, total);
return total.length;
}
// Test
console.log(numberOfArithmeticSlices([2, 4, 6, 8, 10]));#include <stdio.h>
#include <stdbool.h>
bool isArithmetic(int* seq, int length) {
if (length < 3) return false;
int diff = seq[1] - seq[0];
for (int i = 2; i < length; i++) {
if (seq[i] - seq[i - 1] != diff)
return false;
}
return true;
}
void generateSubsequences(int* nums, int numsSize, int* curr, int currSize, int start, int* count) {
if (currSize >= 3 && isArithmetic(curr, currSize)) {
(*count)++;
}
for (int i = start; i < numsSize; i++) {
curr[currSize] = nums[i];
generateSubsequences(nums, numsSize, curr, currSize + 1, i + 1, count);
}
}
int numberOfArithmeticSlices(int* nums, int numsSize) {
int* curr = (int*)malloc(numsSize * sizeof(int));
int count = 0;
generateSubsequences(nums, numsSize, curr, 0, 0, &count);
free(curr);
return count;
}
int main() {
int nums[] = {2, 4, 6, 8, 10};
int numsSize = sizeof(nums) / sizeof(nums[0]);
printf("%d\n", numberOfArithmeticSlices(nums, numsSize));
return 0;
}using System;
using 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));
}
}This Python solution directly generates combinations, checks their arithmetic property, and accumulates the count. The approach demonstrates brute-force searching across combination space, understandable but inefficiently scales poorly.
Time Complexity: O(n * 2^n) due to the exhaustive nature.
Space Complexity: O(n) as subsequences accumulate through recursion/iteration.
Approach 3: Default Approach
function numberOfArithmeticSlices(nums: number[]): number {
const n = nums.length;
const f: Map<number, number>[] = new Array(n).fill(0).map(() => new Map());
let ans = 0;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < i; ++j) {
const d = nums[i] - nums[j];
const cnt = f[j].get(d) || 0;
ans += cnt;
f[i].set(d, (f[i].get(d) || 0) + cnt + 1);
}
}
return ans;
}func numberOfArithmeticSlices(nums []int) (ans int) {
f := make([]map[int]int, len(nums))
for i := range f {
f[i] = map[int]int{}
}
for i, x := range nums {
for j, y := range nums[:i] {
d := x - y
cnt := f[j][d]
ans += cnt
f[i][d] += cnt + 1
}
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| Dynamic Programming with HashMap | Time Complexity: O(n^2), with n the length of nums. |
| Brute Force Approach (Inefficient for Larger Inputs) | Time Complexity: O(n * 2^n) due to the exhaustive nature. |
| Default Approach | – |
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 |
Frequently asked questions
Is Arithmetic Slices II - Subsequence easy or hard?
Arithmetic Slices II - Subsequence is classified as a Hard problem on LeetCode. The difficulty comes from recognizing the dynamic programming pattern and correctly counting subsequences without double counting.
Arithmetic Slices II - Subsequence Python/Java solution
Python and Java implementations follow the same DP idea: maintain a list or array of hash maps and update counts for each pair (j, i). When a difference already exists in dp[j], extend those subsequences and add to the result. The complexity remains O(n^2) time and O(n^2) space across languages.
How to solve Arithmetic Slices II - Subsequence in O(n)?
An O(n) solution is not known for this problem because every pair of elements must be examined to determine their difference. The best known approach is O(n^2) using dynamic programming and hash maps to track subsequence counts by difference.
What is the best approach for Arithmetic Slices II - Subsequence?
Dynamic Programming with a HashMap per index is the most efficient approach. For every pair of indices (j, i), compute the difference and extend existing subsequences stored in dp[j]. This builds longer arithmetic subsequences incrementally and runs in O(n^2) time with O(n^2) space.
Is Arithmetic Slices II - Subsequence asked at Google/Amazon/Meta?
Arithmetic subsequence and difference-tracking problems appear in interviews at companies like Google, Amazon, and Meta. The question tests dynamic programming design, hash map usage, and reasoning about subsequences rather than contiguous subarrays.
What data structure is used in Arithmetic Slices II - Subsequence?
The optimal solution uses an array of hash maps. Each map stores the number of arithmetic subsequences ending at an index for a given difference. This allows constant-time lookup and extension of existing subsequences.
What is the time complexity of Arithmetic Slices II - Subsequence?
The optimal dynamic programming solution runs in O(n^2) time because it processes every pair of indices once. Each step performs constant-time hash map updates. Space complexity is O(n^2) due to storing difference counts for each index.