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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Arithmetic Slices II - Subsequence

Difficulty: Hard

Problem Description

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.

Key Insights

  • An arithmetic sequence requires at least three elements with a constant difference between consecutive elements.
  • We can use dynamic programming to track potential arithmetic subsequences using a hashmap.
  • The problem can be approached by iterating through pairs of numbers and calculating the common difference to find valid subsequences.
  • Each pair of indices can be a starting point for multiple subsequences, allowing us to build up from existing subsequences.

Space and Time Complexity

Time Complexity: O(n^2) - We need to examine each pair of elements in the input array. Space Complexity: O(n) - We use a hashmap to store the count of subsequences for various differences.

Solution

The solution uses a dynamic programming approach where we maintain a hashmap that keeps track of the number of arithmetic subsequences ending at each index for each possible difference. For each pair of indices, we compute their difference and update our hashmap accordingly. This allows us to count valid subsequences efficiently.

Code Solutions

def numberOfArithmeticSlices(nums):
    from collections import defaultdict
    
    n = len(nums)
    dp = [defaultdict(int) for _ in range(n)]
    total_slices = 0

    for j in range(n):
        for i in range(j):
            diff = nums[j] - nums[i]
            if diff in dp[i]:
                count = dp[i][diff]
                dp[j][diff] += count + 1
                total_slices += count
            else:
                dp[j][diff] += 1

    return total_slices

# Example usage
print(numberOfArithmeticSlices([2, 4, 6, 8, 10])) # Output: 7
← Back to All Questions