Sum of Good Subsequences solution and explanation
Google
7 more videos on this problem
3351. Sum of Good Subsequences | DP | Don't Overthink here :)Aryan Mittal · 14:38 · 4K views
3351. Sum of Good Subsequences (Leetcode Hard)Programming Live with Larry · 36:44 · 626 views
Leetcode 3351 | Sum of Good Subsequences | Weekly Contest 423 Solutions | Follow the steps | CodefodCodeFod · 21:05 · 548 views
3351. Sum of Good Subsequences | DP | Math | LeetCode | HardLeet's Code · 16:07 · 372 views
Sum of Good Subsequences | Leetcode 3351 | LeetcodeR Sai Siddhu · 23:29 · 217 views
Sum Of Good Subsequences | Leetcode - 3351 | Java | TamilJet To Mastery · 59:09 · 130 views
Weekly Contest 423 | 3349, 3350, 3351 & 3352 | LeetcodeAmit Choraria · 49:57 · 52 views
100486. Sum of Good Subsequences leetcode weekly-contest-423Leetcode Solutions · 0:28 · 24 views
The problem
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 <= 1050 <= 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.
def sum_of_good_subsequences(nums):
MOD = 10**9 + 7
def valid_sequence(seq):
return all(abs(seq[i] - seq[i + 1]) == 1 for i in range(len(seq) - 1))
def subsequences(arr):
if len(arr) == 0:
return [[]]
all_subseq = subsequences(arr[1:])
return all_subseq + [[arr[0]] + seq for seq in all_subseq]
total_sum = 0
for subseq in subsequences(nums):
if valid_sequence(subseq):
total_sum = (total_sum + sum(subseq)) % MOD
return total_sum
# Example usage
nums = [1, 2, 1]
print(sum_of_good_subsequences(nums)) # Output: 14function sumOfGoodSubsequences(nums) {
const MOD = 1000000007;
function isValidSequence(seq) {
for (let i = 0; i < seq.length - 1; i++) {
if (Math.abs(seq[i] - seq[i + 1]) !== 1) return false;
}
return true;
}
function subsequences(arr) {
if (arr.length === 0) return [[]];
const first = arr[0];
const rest = subsequences(arr.slice(1));
return rest.concat(rest.map(subseq => [first, ...subseq]));
}
const allSubseq = subsequences(nums);
let totalSum = 0;
for (const subseq of allSubseq) {
if (isValidSequence(subseq)) {
totalSum = (totalSum + subseq.reduce((a, b) => a + b, 0)) % MOD;
}
}
return totalSum;
}
// Example usage
const nums = [1, 2, 1];
console.log(sumOfGoodSubsequences(nums)); // Output: 14The 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.
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.
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.
def sum_of_good_subsequences(nums):
MOD = 10**9 + 7
max_val = max(nums)
freq = [0] * (max_val + 1)
for num in nums:
freq[num] += 1
dp = [0] * (max_val + 1)
result = 0
for i in range(max_val + 1):
if freq[i] > 0:
dp[i] = (freq[i] * (1 + (dp[i - 1] if i > 0 else 0) + dp[i])) % MOD
result = (result + dp[i]) % MOD
return result
# Example usage
nums = [1, 2, 1]
print(sum_of_good_subsequences(nums)) # Output: 14public class Solution {
public int sumOfGoodSubsequences(int[] nums) {
final int MOD = (int)1e9 + 7;
int maxVal = 0;
for (int num : nums) {
maxVal = Math.max(maxVal, num);
}
int[] freq = new int[maxVal + 1];
for (int num : nums) {
freq[num]++;
}
int[] dp = new int[maxVal + 1];
int result = 0;
for (int i = 0; i <= maxVal; i++) {
if (freq[i] > 0) {
dp[i] = (int)((long)freq[i] * (1L + (i > 0 ? dp[i - 1] : 0L) + dp[i]) % MOD);
result = (result + dp[i]) % MOD;
}
}
return result;
}
public static void main(String[] args) {
Solution sol = new Solution();
int[] nums = {1, 2, 1};
System.out.println(sol.sumOfGoodSubsequences(nums)); // Output: 14
}
}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.
Time Complexity: O(n + max_value), where max_value is the maximum number in nums. Space Complexity: O(max_value).
Approach 3: Default Approach
class Solution {
public:
int sumOfGoodSubsequences(vector<int>& nums) {
const int mod = 1e9 + 7;
int mx = ranges::max(nums);
vector<long long> f(mx + 1), g(mx + 1);
for (int x : nums) {
f[x] += x;
g[x] += 1;
if (x > 0) {
f[x] = (f[x] + f[x - 1] + g[x - 1] * x % mod) % mod;
g[x] = (g[x] + g[x - 1]) % mod;
}
if (x + 1 <= mx) {
f[x] = (f[x] + f[x + 1] + g[x + 1] * x % mod) % mod;
g[x] = (g[x] + g[x + 1]) % mod;
}
}
return accumulate(f.begin(), f.end(), 0LL) % mod;
}
};function sumOfGoodSubsequences(nums: number[]): number {
const mod = 10 ** 9 + 7;
const mx = Math.max(...nums);
const f: number[] = Array(mx + 1).fill(0);
const g: number[] = Array(mx + 1).fill(0);
for (const x of nums) {
f[x] += x;
g[x] += 1;
if (x > 0) {
f[x] = (f[x] + f[x - 1] + ((g[x - 1] * x) % mod)) % mod;
g[x] = (g[x] + g[x - 1]) % mod;
}
if (x + 1 <= mx) {
f[x] = (f[x] + f[x + 1] + ((g[x + 1] * x) % mod)) % mod;
g[x] = (g[x] + g[x + 1]) % mod;
}
}
return f.reduce((acc, cur) => (acc + cur) % mod, 0);
}func sumOfGoodSubsequences(nums []int) (ans int) {
mod := int(1e9 + 7)
mx := slices.Max(nums)
f := make([]int, mx+1)
g := make([]int, mx+1)
for _, x := range nums {
f[x] += x
g[x] += 1
if x > 0 {
f[x] = (f[x] + f[x-1] + g[x-1]*x%mod) % mod
g[x] = (g[x] + g[x-1]) % mod
}
if x+1 <= mx {
f[x] = (f[x] + f[x+1] + g[x+1]*x%mod) % mod
g[x] = (g[x] + g[x+1]) % mod
}
}
for _, x := range f {
ans = (ans + x) % mod
}
return
}Complexity comparison
| Approach | Complexity |
|---|---|
| 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 | – |
Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Enumeration | O(2^n) | O(n) | Understanding the definition of good subsequences or testing small inputs |
| Dynamic Programming with Hash Map | O(n) | O(n) | General case and interview solution where large arrays require efficient aggregation |
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.