Sum of Good Subsequences

Hard
1669.

Sum of Good Subsequences

Sum of Good Subsequences is a hard coding problem on arrays, hash table and dynamic programming, asked in Amazon interviews.

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^5
  • 0 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var sumOfGoodSubsequences = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^5
  • 0 <= nums[i] <= 10^5

Hints for Sum of Good Subsequences

  1. Hint 1

    A good subsequence ending at value x was extended from one ending at x - 1 or x + 1 (or it starts at x).

  2. Hint 2

    For each value keep two numbers: how many good subsequences end with that value, and the total of their element sums.

  3. Hint 3

    Appending x to c subsequences adds x · c to their combined sum. So for a new x: c = 1 + cnt[x-1] + cnt[x+1], s = sum[x-1] + sum[x+1] + x · c; add both to value x'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

  1. Keep arrays cnt[v] and sum[v] over values (offset by one so x - 1 is valid for x = 0).
  2. For each x: c = 1 + cnt[x - 1] + cnt[x + 1] and s = sum[x - 1] + sum[x + 1] + x · c, all modulo 10^9 + 7.
  3. Add c to cnt[x] and s to sum[x].
  4. 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 · c can reach about 10^5 × 10^9 — use 64-bit arithmetic before taking the modulus.
  • Read cnt[x - 1], cnt[x + 1] before updating cnt[x]; with equal neighbours there is no conflict, but keep the order clear.
  • Value 0 has no x - 1 neighbour — 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) % MOD

Java

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