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

Sum of Good Subsequences

Number: 3646

Difficulty: Hard

Paid? No

Companies: Google

Problem Description

Given an integer array nums, a "good subsequence" is defined as a subsequence in which the absolute difference between any two consecutive elements is exactly 1. Note that any subsequence with only one element is automatically good. The task is to compute the sum of the elements over all possible good subsequences of nums, and return the answer modulo 10^9 + 7.

Key Insights

  • A subsequence is formed by removing zero or more elements without changing the order.
  • For a subsequence to be good, every consecutive pair must satisfy |a - b| = 1.
  • When processing an element, it can either start a new subsequence by itself or extend a previously formed good subsequence if its last element differs by exactly 1 (either plus or minus 1).
  • We can use dynamic programming where for each possible ending value we maintain:
    • count: the number of good subsequences ending with that value.
    • total sum: the cumulative sum of all those good subsequences.
  • When a new element x is processed, it contributes as a single element subsequence and may extend subsequences ending with x-1 and x+1.
  • The final answer is obtained by summing the totals for all keys.

Space and Time Complexity

Time Complexity: O(n), where n is the length of nums (each element is processed once).
Space Complexity: O(m), where m is the number of distinct values (at most 10^5).

Solution

We use a dynamic programming (DP) approach with two hash tables (or dictionaries) keyed by element value: one (dp_count) to store the count of good subsequences ending with that value, and another (dp_sum) to store the cumulative sum of elements in those subsequences.

For each element x in nums, consider:

  • Starting a new subsequence with just x: contributes a count of 1 and a sum of x.
  • Extending any subsequence that currently ends with (x-1) (because |(x-1) - x| = 1) as well as those that end with (x+1) (| (x+1) - x| = 1).
    • For each subsequence extended, if the count of subsequences ending with a predecessor is count, then:
      • The new count increases by that count.
      • The new sum increases by the previous cumulative sum plus count multiplied by x (because x is added to each extended subsequence).

The new contributions (new_count and new_sum) are then added to dp_count[x] and dp_sum[x] (taking into account previous occurrences of x in the array). After iterating through all elements, the final answer is the sum over all dp_sum values modulo 10^9 + 7.

Code Solutions

# Define the modulo constant
MOD = 10**9 + 7

def sumOfGoodSubsequences(nums):
    # Dictionaries to keep track of counts and sum of good subsequences ending with a particular value.
    dp_count = {}  # dp_count[x] = number of good subsequences ending with x
    dp_sum = {}    # dp_sum[x] = sum of elements for all good subsequences ending with x

    for x in nums:
        # Each new number forms a new subsequence of itself.
        new_count = 1
        new_sum = x

        # Extend subsequences where the last element is x-1.
        if (x - 1) in dp_count:
            new_count = (new_count + dp_count[x - 1]) % MOD
            # For each subsequence ending with (x-1), when extended by x, add the previous sum plus x*count.
            new_sum = (new_sum + dp_sum[x - 1] + x * dp_count[x - 1]) % MOD

        # Extend subsequences where the last element is x+1.
        if (x + 1) in dp_count:
            new_count = (new_count + dp_count[x + 1]) % MOD
            new_sum = (new_sum + dp_sum[x + 1] + x * dp_count[x + 1]) % MOD

        # Add the new subsequences to those ending with x.
        dp_count[x] = (dp_count.get(x, 0) + new_count) % MOD
        dp_sum[x] = (dp_sum.get(x, 0) + new_sum) % MOD

    # Sum over all the cumulative sums of good subsequences, modulo MOD.
    total_sum = sum(dp_sum.values()) % MOD
    return total_sum

# Example usage:
# print(sumOfGoodSubsequences([1,2,1]))  # Expected output: 14
← Back to All Questions