We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Arithmetic Slices II - Subsequence

Number: 446

Difficulty: Hard

Paid? No

Companies: Google, Microsoft, Amazon, Apple, Baidu

Problem Description

Given an integer array nums, return the number of all arithmetic subsequence slices in the array. An arithmetic sequence is defined as having at least three elements where the difference between any two consecutive elements is the same. Note that a subsequence can be obtained by removing some elements (possibly none) from the array.

Key Insights

  • Use dynamic programming to count arithmetic subsequences ending at every index.
  • Maintain a hashmap (or dictionary) for each index that maps a difference to the count of subsequences ending at that index with that difference.
  • For every pair (i, j) with i < j, compute the difference diff = nums[j] - nums[i]; then update the count at index j based on existing subsequences ending at index i with the same difference.
  • Only subsequences of length at least three are considered valid arithmetic slices; two-element sequences are used as building blocks only.

Space and Time Complexity

Time Complexity: O(n²) since we iterate over all pairs of indices. Space Complexity: O(n²) in the worst case for storing the hashmap counts per index.

Solution

We use a dynamic programming approach where for each index j, we keep a dictionary (or hashmap) mapping each possible difference to the number of arithmetic subsequences ending at j with that difference. For every pair of indices (i, j) with i < j, we do the following:

  1. Calculate the difference diff = nums[j] - nums[i].
  2. Retrieve the count of sequences ending at index i with this difference.
  3. Update the count of sequences ending at index j for diff (adding the count from i plus one new two-element pair).
  4. Add the count from index i (which represents sequences with length >= 2 at i) to the result since extending them by nums[j] forms valid sequences of length >= 3.

This method carefully differentiates between two-element sequences (which serve as precursors) and sequences of length 3 or more that contribute to the final answer.

Code Solutions

# Python solution for Arithmetic Slices II - Subsequence

class Solution:
    def numberOfArithmeticSlices(self, nums: list[int]) -> int:
        n = len(nums)
        if n < 3:
            return 0
        
        # dp[i] is a dictionary mapping a difference to the number of arithmetic subsequences ending at index i with that difference.
        dp = [dict() for _ in range(n)]
        result = 0
        
        # Iterate over each pair (i, j)
        for j in range(n):
            for i in range(j):
                diff = nums[j] - nums[i]
                # get count of sequences ending at i with this diff
                count_at_i = dp[i].get(diff, 0)
                # Update the dp for index j for diff: extend the sequences ending at i and the new pair (i,j)
                dp[j][diff] = dp[j].get(diff, 0) + count_at_i + 1
                # Only sequences that extend an already existing subsequence contribute to result (they now become length >= 3)
                result += count_at_i
        
        return result

# Example usage:
# sol = Solution()
# print(sol.numberOfArithmeticSlices([2,4,6,8,10]))
← Back to All Questions