Skip to main content

446. Arithmetic Slices II - Subsequence

hard

Count arithmetic subsequences of length 3 or more. The natural-recursion-over-pairs problem where memoization with a hash map keyed on (index, difference) is the cleanest path.

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. 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

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

Define dp[i][d] = number of arithmetic subsequences ending at index i with common difference d that have length >= 2.

Hint 2

For each pair (j, i) where j < i: d = nums[i] - nums[j]; sum += dp[j][d]; dp[i][d] += dp[j][d] + 1.

Hint 3

The +1 accounts for the new 2-length subsequence (nums[j], nums[i]). The sum adds the count of extensions that grew to length >= 3.

Hint 4

Use a hash map per index, keyed on difference.

Solution approach

Reveal approach

Maintain dp[i] as a hash map from difference -> count of arithmetic subsequences of length >= 2 ending at i. For each pair (j, i) with j < i: compute d = nums[i] - nums[j]. The number of length-2 'subsequences' ending at j with difference d is dp[j].get(d, 0); add this to dp[i][d] AND to the answer (because extending each by nums[i] produces a length-3 or longer subsequence, which is what we count). Also add 1 to dp[i][d] for the new (nums[j], nums[i]) length-2 subsequence — but this isn't counted in the answer because length is only 2. The recursion is implicit in the dp transition. Time is O(n^2); space O(n^2) worst case.

Complexity

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

Related patterns

  • dynamic-programming
  • recursion
  • hash-map

Related problems

Asked at

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

  • Google
  • Amazon

Practice these live with InterviewChamp.AI

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

Practice these live with InterviewChamp.AI →