Sum of Good Subsequences — Solution in Python, Java & C++
Sum of Good Subsequences solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem, asked at Amazon.
Sum of Good Subsequences is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon interviews.
- Difficulty: Hard
- Topics: Arrays, Hash Table, Dynamic Programming
- Asked at: Amazon
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
You are given an integer array nums. A subsequence of nums is good if the absolute difference between every two consecutive elements of the subsequence is exactly 1. Every subsequence of length 1 is good.
Return the sum of the elements of all good subsequences of nums, counting each subsequence (chosen by its indices) once. Since the answer may be very large, return it modulo 10^9 + 7.
Example 1
Input: nums = [1,2,1]
Output: 14
Explanation: The good subsequences are [1], [2], [1], [1,2], [2,1] and [1,2,1]; their elements add up to 14.
Example 2
Input: nums = [3,4,5]
Output: 40
Explanation: [3], [4], [5], [3,4], [4,5] and [3,4,5] sum to 3 + 4 + 5 + 7 + 9 + 12 = 40.
Example 3
Input: nums = [5]
Output: 5
Constraints
1 <= nums.length <= 10^50 <= nums[i] <= 10^5
Hints for Sum of Good Subsequences
Hint 1
A good subsequence ending at value
xwas extended from one ending atx - 1orx + 1(or it starts atx).Hint 2
For each value keep two numbers: how many good subsequences end with that value, and the total of their element sums.
Hint 3
Appending
xtocsubsequences addsx · cto their combined sum. So for a newx:c = 1 + cnt[x-1] + cnt[x+1],s = sum[x-1] + sum[x+1] + x · c; add both to valuex's entries.
How to solve Sum of Good Subsequences
Process the array left to right and, for every value v, remember how many good subsequences so far end with v and the sum of all their elements. A new element x starts one subsequence and extends every subsequence ending with x - 1 or x + 1.
Approach
- Keep arrays
cnt[v]andsum[v]over values (offset by one sox - 1is valid forx = 0). - For each
x:c = 1 + cnt[x - 1] + cnt[x + 1]ands = sum[x - 1] + sum[x + 1] + x · c, all modulo10^9 + 7. - Add
ctocnt[x]andstosum[x]. - Return the total of
sum[v]over all values.
Why it works
Every good subsequence ending at index i is either [nums[i]] or a good subsequence ending at an earlier index whose value differs from nums[i] by exactly 1, with nums[i] appended. Grouping those earlier subsequences by their last value gives exactly cnt[x ± 1] of them with total sum[x ± 1], and appending x to each adds x once per subsequence.
Complexity
- Time —
O(n + V) - Space —
O(V)
Pitfalls
x · ccan reach about10^5 × 10^9— use 64-bit arithmetic before taking the modulus.- Read
cnt[x - 1],cnt[x + 1]before updatingcnt[x]; with equal neighbours there is no conflict, but keep the order clear. - Value 0 has no
x - 1neighbour — shift the indices instead of reading index -1.
Reference solution
Python
from typing import List
def sumOfGoodSubsequences(nums: List[int]) -> int:
MOD = 10**9 + 7
size = max(nums) + 3
cnt = [0] * size
sm = [0] * size
for x in nums:
i = x + 1 # shifted so that i - 1 is always valid
c = (1 + cnt[i - 1] + cnt[i + 1]) % MOD
s = (sm[i - 1] + sm[i + 1] + x * c) % MOD
cnt[i] = (cnt[i] + c) % MOD
sm[i] = (sm[i] + s) % MOD
return sum(sm) % MODJava
public static int sumOfGoodSubsequences(int[] nums) {
final long MOD = 1000000007L;
int M = 0;
for (int x : nums) M = Math.max(M, x);
long[] cnt = new long[M + 3], sm = new long[M + 3];
for (int x : nums) {
int i = x + 1;
long c = (1 + cnt[i - 1] + cnt[i + 1]) % MOD;
long s = (sm[i - 1] + sm[i + 1] + (long) x * c) % MOD;
cnt[i] = (cnt[i] + c) % MOD;
sm[i] = (sm[i] + s) % MOD;
}
long total = 0;
for (long v : sm) total = (total + v) % MOD;
return (int) total;
}C++
int sumOfGoodSubsequences(vector<int>& nums) {
const long long MOD = 1000000007LL;
int M = *max_element(nums.begin(), nums.end());
vector<long long> cnt(M + 3, 0), sm(M + 3, 0);
for (int x : nums) {
int i = x + 1;
long long c = (1 + cnt[i - 1] + cnt[i + 1]) % MOD;
long long s = (sm[i - 1] + sm[i + 1] + (long long) x * c) % MOD;
cnt[i] = (cnt[i] + c) % MOD;
sm[i] = (sm[i] + s) % MOD;
}
long long total = 0;
for (long long v : sm) total = (total + v) % MOD;
return (int) total;
}JavaScript
var sumOfGoodSubsequences = function(nums) {
var MOD = 1000000007;
var M = 0;
for (var k = 0; k < nums.length; k++) if (nums[k] > M) M = nums[k];
var cnt = new Array(M + 3).fill(0), sm = new Array(M + 3).fill(0);
for (var j = 0; j < nums.length; j++) {
var x = nums[j], i = x + 1;
var c = (1 + cnt[i - 1] + cnt[i + 1]) % MOD;
// x < 2^17 and c < 2^30, so x * c stays exact in a double.
var s = (sm[i - 1] + sm[i + 1] + (x * c) % MOD) % MOD;
cnt[i] = (cnt[i] + c) % MOD;
sm[i] = (sm[i] + s) % MOD;
}
var total = 0;
for (var v = 0; v < sm.length; v++) total = (total + sm[v]) % MOD;
return total;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets