Is Sum of Good Subsequences easy or hard?

LeetCode classifies this problem as Hard. The challenge comes from aggregating sums across exponentially many subsequences without generating them explicitly. Recognizing the value-based dynamic programming transition is the key insight.

Sum of Good Subsequences Python/Java solution

Python and Java implementations both follow the same DP logic: maintain maps for counts and sums, extend subsequences from v-1 and v+1, and update the result modulo 1e9+7. Python typically uses defaultdict or dict, while Java implementations use HashMap or arrays if the value range is known.

How to solve Sum of Good Subsequences in O(n)?

Maintain two hash maps: count[v] for the number of good subsequences ending with value v and sum[v] for their total sums. For each element v, create a single-element subsequence and extend subsequences ending at v-1 and v+1. Update the maps and add the new contribution to the result. Each step uses constant-time updates, giving O(n) complexity.

What is the best approach for Sum of Good Subsequences?

The most efficient solution uses dynamic programming with a hash map. Track how many good subsequences end at each value and the total sum contributed by those subsequences. When processing a number v, extend subsequences ending at v-1 and v+1 and update the counts and sums. This achieves O(n) time with O(n) extra space.

Is Sum of Good Subsequences asked at Google/Amazon/Meta?

Problems combining dynamic programming with hash maps and subsequence counting frequently appear in interviews at companies like Google, Amazon, and Meta. Variants that track subsequence counts or sums based on value transitions are common in senior-level coding rounds.

What data structure is used in Sum of Good Subsequences?

The optimized solution relies on a hash table (dictionary/map) to store counts and cumulative sums for subsequences ending at specific values. Dynamic programming defines the transition, while the hash map enables O(1) neighbor lookups for v-1 and v+1.

What is the time complexity of Sum of Good Subsequences?

The optimal dynamic programming approach runs in O(n) time because each array element performs constant-time hash lookups for values v-1 and v+1. Space complexity is O(n) for storing counts and accumulated sums of subsequences ending at different values.

Description Hints 2 Solution Video 14:38

3351. Sum of Good Subsequences

Hard30.9% acceptance1 company

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⁹ + 7.

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

Example 1:

Input: nums = [1,2,1]

Output: 14

Explanation:

Good subsequences are: [1], [2], [1], [1,2], [2,1], [1,2,1].
The sum of elements in these subsequences is 14.

Example 2:

Input: nums = [3,4,5]

Output: 40

Explanation:

Good subsequences are: [3], [4], [5], [3,4], [4,5], [3,4,5].
The sum of elements in these subsequences is 40.

Constraints:

1 <= nums.length <= 10⁵
0 <= nums[i] <= 10⁵

Asked at 1 company

Google

Topics

Hints open one at a time

Hint 1

Consider counting how many times each element occurs in all possible good subsequences. This can help you derive the final answer more easily.

Hint 2

Use dynamic programming to track both the count and the sum of subsequences where the last element is nums[i].

14:38

Still stuck?Read 3 approaches, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
2    def sumOfGoodSubsequences(self, nums: List[int]) -> int:
3        

Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2,1]

Input

[3,4,5]

Your code is saved on this device.Solution