Problem Description

You are given an integer array nums. A good subsequence is defined as a subsequence of nums where the absolute difference between any two consecutive elements in the subsequence is exactly 1.

Return the sum of all possible good subsequences of nums.

Since the answer may be very large, return it modulo 10^9 + 7.

Note that a subsequence of size 1 is considered good by definition.

Intuition

To solve this problem, the goal is finding and calculating the sum of all good subsequences of the given array nums where consecutive elements have an absolute difference of 1.

A straightforward approach might involve generating all possible subsequences, checking their validity according to the given conditions, and computing the sum. However, this method is inefficient because the number of potential subsequences grows exponentially with the array's size.

Instead, a more efficient approach leverages dynamic programming by maintaining two maps (f and g) to store the intermediate results during the computation. Here:

• f[x] represents the cumulative sum of good subsequences up to the element x.
• g[x] counts the number of times element x contributes to forming a good subsequence.

For every element x in nums, calculate and update f[x] and g[x] by considering its contribution in conjunction with its neighboring elements (x-1 and x+1). This accounts for all subsequences that can be extended with x.

The algorithm efficiently computes the sum of all possible good subsequences by iteratively processing each element and updating the maps. Finally, it returns the sum of values in f, taken modulo 10^9 + 7, to handle large numbers.

Learn more about Dynamic Programming patterns.

Solution Approach

The solution employs a dynamic programming approach, making use of two main data structures: dictionaries f and g from the collections module.

Here's a step-by-step explanation of the solution:

1. Initialize Constants and Data Structures:

   • Set mod to 10^9 + 7 to manage large numbers via modular arithmetic.
   • Use f to store the cumulative sums of good subsequences ending with each unique number.
   • Use g to count occurrences of good subsequences that can be extended by each number.

2. Iterate Over the Input Array:

   • For each number x in the array nums, update the data structures:
     • Increment f[x] by the current value of x, which represents its individual contribution as a single-element subsequence.
     • Increment g[x] to account for x itself as a subsequence.

3. Consider Neighboring Elements:

   • For each x, check its neighbors x-1 and x+1.
   • Update f[x] and f[x] by adding contributions from these neighbors:
     • Add to f[x] the sum of f[x-1] and contributions from g[x-1] multiplied by x, computing the sum of subsequences that can be extended.
     • Similarly, add contributions involving x+1.

4. Sum and Modulo Operation:

   • Finally, compute the sum of all values in f to get the total sum of all good subsequences.
   • Return this sum modulo 10^9 + 7 to handle potentially large numbers.

This method efficiently constructs a solution by recognizing patterns and leveraging relationships between consecutive elements, significantly reducing the computational complexity compared to brute force approaches.

The given code implements this logic:

class Solution:
    def sumOfGoodSubsequences(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        f = defaultdict(int)
        g = defaultdict(int)
        for x in nums:
            f[x] += x
            g[x] += 1
            f[x] += f[x - 1] + g[x - 1] * x
            g[x] += g[x - 1]
            f[x] += f[x + 1] + g[x + 1] * x
            g[x] += g[x + 1]
        return sum(f.values()) % mod

Example Walkthrough

Let's consider a small example to illustrate the solution approach:

Suppose the input array nums is [1, 2, 3].

1. Initialize Constants and Data Structures:

   • mod = 10^9 + 7
   • f, g: both initialized as default dictionaries to store cumulative sums and subsequence counts, respectively.

2. Iterate Over the Input Array:

   • For x = 1:

     • f[1] += 1 (since 1 can form a subsequence by itself)
     • g[1] += 1 (counting the subsequence [1])
     • Consider x-1 (0) and x+1 (2):
       • f[1] remains the same, as x-1 is not part of nums.
       • f[2] will be updated when x = 2 is processed.

   • For x = 2:

     • f[2] += 2 (subsequence [2])
     • g[2] += 1
     • Consider x-1 (1) and x+1 (3):
       • f[2] += f[1] + g[1] * 2:
         • f[2] now accounts for subsequences [1, 2], [2].
       • f[3] will be updated when x = 3 is processed.

   • For x = 3:

     • f[3] += 3 (subsequence [3])
     • g[3] += 1
     • Consider x-1 (2) and x+1 (4):
       • f[3] += f[2] + g[2] * 3:
         • f[3] now accounts for subsequences [1, 2, 3], [2, 3], [3].

3. Sum and Modulo Operation:

   • Calculate sum(f.values()): this gives the sum of all good subsequences, which are [1], [2], [1, 2], [3], [2, 3], [1, 2, 3].
   • Return the result modulo 10^9 + 7.

Using dynamic programming through the f and g mappings allows the calculation of good subsequences efficiently.

Solution Implementation

Time and Space Complexity

The time complexity of the code is O(n), where n is the number of elements in the nums list. This is because each element in the list is processed once through a series of constant-time operations.

The space complexity of the code is O(n). This results from using two defaultdict objects, f and g, which store information related to each unique element in nums. In the worst case, these dictionaries could hold as many entries as there are elements in nums.

Learn more about how to find time and space complexity quickly.