#3351

Hard

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Sum of Good Subsequences

Calculate the sum of all good subsequences in an array where consecutive numbers differ by exactly one.

Problem Statement

Given an integer array nums, define a good subsequence as any subsequence where the absolute difference between consecutive elements is exactly 1. Your task is to compute all such good subsequences.

Return the total sum of every good subsequence in nums. Since the sum can be very large, return it modulo 1000000007.

Examples

Example 1

Input: nums = [1,2,1]

Output: 14

Example 2

Input: nums = [3,4,5]

Output: 40

Constraints

1 <= nums.length <= 105
0 <= nums[i] <= 105

Solution Approach

Use a Hash Map to Track Subsequence Sums

Maintain a hash map where each key is a number from nums and the value is the cumulative sum of all good subsequences ending with that number. This allows efficient lookups to extend existing subsequences by checking keys n-1 and n+1 for each number n.

Iterate Through the Array and Update Counts

Scan nums sequentially. For each element, calculate its contribution by adding its value to the sums of subsequences that could extend to it, i.e., sums ending with element-1 and element+1. Update the hash map after each element to build subsequences dynamically.

Aggregate Total Sum with Modulo Handling

After processing all elements, sum all values in the hash map to get the total sum of good subsequences. Apply modulo 1000000007 at every addition to prevent integer overflow, ensuring the final answer fits the constraints.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n) if hash map operations are O(1), as each array element is scanned once. Space complexity is O(m) where m is the number of distinct numbers in nums due to storing sums in the hash map.

What Interviewers Usually Probe

Focus on array scanning plus hash lookup pattern.
Check if candidate handles modulo constraints correctly.
Look for dynamic aggregation of subsequence sums without generating all subsequences.

Common Pitfalls or Variants

Common pitfalls

Attempting to generate all subsequences explicitly leading to TLE.
Forgetting to include contributions from both element-1 and element+1.
Neglecting modulo arithmetic, causing overflow for large arrays.

Follow-up variants

Count the number of good subsequences instead of summing them.
Restrict good subsequences to fixed length k and sum their values.
Allow absolute difference of up to k instead of exactly 1.

FAQ

What defines a good subsequence in this problem?

A good subsequence is one where the absolute difference between consecutive elements is exactly 1.

Why is a hash map needed for this solution?

The hash map tracks cumulative sums for each number, enabling constant-time extension of existing good subsequences.

How does this pattern differ from normal subsequence sum problems?

This pattern specifically requires checking neighbors n-1 and n+1 to dynamically build sums, not just arbitrary subsequences.

What is the modulo used in the sum?

All calculations use modulo 1000000007 to prevent integer overflow.

Can this approach handle large arrays efficiently?

Yes, by scanning once and using a hash map, the algorithm avoids generating all subsequences, keeping it efficient for arrays up to length 10^5.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

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

Continue Practicing

#3316 find maximum removals from source string #3434 maximum frequency after subarray operation #3505 minimum operations to make elements within k subarrays equal