Skip to main content
Talentd

Sum of Good Subsequences - Solution & Explanation

HardArrayHash TableDynamic Programming9 min readAsked at: Google
Practice this problem

Problem Statement

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 109 + 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 <= 105
  • 0 <= nums[i] <= 105

Approach Overview

Problem Overview: You are given an integer array and need the total sum of all good subsequences. A subsequence is considered good when the absolute difference between every pair of adjacent elements equals 1. Instead of listing subsequences explicitly, the goal is to efficiently accumulate the sum contributed by every valid subsequence.

Approach 1: Brute Force Enumeration (O(2^n) time, O(n) space)

Generate every subsequence using recursion or bitmasking. For each subsequence, check whether the absolute difference between adjacent elements equals 1. If the subsequence is valid, compute its element sum and add it to the global result. This approach directly follows the definition but quickly becomes impractical because the number of subsequences grows exponentially. It only works for very small arrays and mainly serves as a conceptual baseline.

Approach 2: Dynamic Programming with Hash Map (O(n) time, O(n) space)

The key observation: a good subsequence ending with value x can only extend from subsequences ending with x-1 or x+1. Maintain two hash maps: count[v] for the number of good subsequences ending with value v, and sum[v] for the total sum of all such subsequences. When processing a new element v, create new subsequences in three ways: the single-element subsequence [v], extensions of subsequences ending in v-1, and extensions of those ending in v+1.

When extending a subsequence ending at k, the new sum increases by v. So the contribution from that side becomes sum[k] + count[k] * v. Add contributions from both neighbors and update the maps for value v. Accumulate the newly created sums into the final answer. A hash map ensures constant-time lookups for v-1 and v+1, making the algorithm linear with respect to the array length.

This approach relies on incremental aggregation instead of explicitly building subsequences. Each number only interacts with two neighboring states, which keeps the transitions simple and efficient.

Recommended for interviews: Interviewers expect the dynamic programming solution combined with a hash table. The brute force method demonstrates understanding of subsequences but fails on constraints. The DP transition using neighbor values shows strong reasoning about state compression and works efficiently with arrays of large size.

Approach 1: Brute Force Approach

This approach involves generating all subsequences of the given array and checking if each subsequence is good, i.e., consecutive elements have an absolute difference of 1.

Once we identify a good subsequence, we calculate the sum of its elements. We take care of possible overflows by applying the modulus operation with 10^9 + 7 after every addition.

Though simple, this approach is inefficient for large arrays due to its exponential time complexity.

The code defines a helper function valid_sequence to check if a subsequence is good. Another helper subsequences generates all subsequences of the list recursively. It computes the total sum of elements in all good subsequences and returns it.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(2^n * n), where n is the length of the array, due to generating all subsequences. Space Complexity: O(2^n), due to storing all subsequences.

Try this approach in the editor →

Approach 2: Dynamic Programming Approach

Instead of generating all subsequences, we can opt for a more efficient approach using dynamic programming.

Create a frequency array to count occurrences of each element. Iterate through possible values, updating a dp array, which keeps the sum of all subsequences ending with a particular value.
For each number i, you can either start a subsequence or extend subsequences ending with i-1, i, or i+1, respecting the absolute difference constraint.
Modulo operation ensures we handle large numbers properly.

This Python code utilizes an array dp that stores cumulative subsequences sums ending at each number. We update our dp array based on current frequency and potential pre-existing subsequences.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n + max_value), where max_value is the maximum number in nums. Space Complexity: O(max_value).

Try this approach in the editor →

Approach 3: Default Approach

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Brute Force Approach

Time Complexity: O(2^n * n), where n is the length of the array, due to generating all subsequences. Space Complexity: O(2^n), due to storing all subsequences.

Dynamic Programming Approach

Time Complexity: O(n + max_value), where max_value is the maximum number in nums. Space Complexity: O(max_value).

Default Approach—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force EnumerationO(2^n)O(n)Understanding the definition of good subsequences or testing small inputs
Dynamic Programming with Hash MapO(n)O(n)General case and interview solution where large arrays require efficient aggregation

Video Solution

3351. Sum of Good Subsequences | DP | Don't Overthink here :) • Aryan Mittal • 4,871 views views

Watch 7 more video solutions →

Frequently Asked Questions

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.

Ready to solve this problem?

Practice Sum of Good Subsequences with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays