Skip to main content

446. Arithmetic Slices II - Subsequence

hard

Count every arithmetic subsequence of length >= 3. Per-index hash map keyed by common difference accumulates weak-arithmetic chains (length >= 2) and tallies strong ones.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

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. A subsequence of an array is a sequence that can be formed by removing some elements (possibly none) of the array. The test cases are generated so that the answer fits in 32-bit integer.

Constraints

  • 1 <= nums.length <= 1000
  • -2^31 <= nums[i] <= 2^31 - 1

Examples

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.

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Track weak arithmetic chains (length >= 2) per (endpoint, difference). Promote them to strong (length >= 3) when extended.

Hint 2

dp[i][d] = number of weak chains ending at i with difference d. When you extend with a new j > i, add dp[i][d] to dp[j][d] and to the answer.

Hint 3

Every existing weak chain becomes a counted strong subsequence when extended once more.

Solution approach

Reveal approach

Use an array of hash maps dp[0..n-1] where dp[i][d] counts the number of weak arithmetic subsequences ending at index i with common difference d (weak = length at least 2). For each pair (j, i) with j < i compute d = nums[i] - nums[j]. The number of weak chains ending at j with this difference is w = dp[j].get(d, 0). Add w + 1 to dp[i][d] — the +1 starts a fresh weak chain (j, i), and the w accounts for extending each existing chain ending at j. Add w to the answer because every extended chain now has length at least 3 and counts as a strong arithmetic subsequence. O(n^2) time and space. Use 64-bit accumulation if differences can overflow.

Complexity

Time
O(n^2)
Space
O(n^2)

Related patterns

  • dynamic-programming
  • hash-map

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Amazon
  • Google

Practice these live with InterviewChamp.AI

Drill Arithmetic Slices II - Subsequence and DP 1D problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →