Sum of Good Subsequences - Practice Coding Problems

Sum of Good Subsequences - 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 10^9 + 7.

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

Input & Output

Example 1 — Basic Case

$ Input: nums = [1,2,1]

› Output: 12

💡 Note: Good subsequences: [1] (sum=1), [2] (sum=2), [1] (sum=1), [1,2] (sum=3), [2,1] (sum=3), [1,2,1] (sum=4). Total: 1+2+1+3+3+4 = 14. Wait, let me recalculate: [1]=1, [2]=2, [1]=1, [1,2]=3, [2,1]=3. Total = 1+2+1+3+3 = 10. Actually for [1,2,1]: we have multiple [1] at positions 0,2, [2] at position 1, [1,2] using positions 0,1, [2,1] using positions 1,2. Sum = 1+2+1+3+3 = 10.

Example 2 — Single Element

$ Input: nums = [3]

› Output: 3

💡 Note: Only one good subsequence: [3] with sum 3

Example 3 — No Extensions

$ Input: nums = [1,3,5]

› Output: 9

💡 Note: No consecutive elements differ by exactly 1. Good subsequences are only single elements: [1], [3], [5]. Total: 1+3+5 = 9

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,1] with elements that can form good subsequences

Process

Find all subsequences where |a[i] - a[i+1]| = 1

Output

Sum all valid subsequences: 1+2+1+3+3+4 = 14

Key Takeaway

🎯 Key Insight: Use DP to track subsequences ending at each value, extending those at val±1

Asked in

G Google 15 a Amazon 12 M Microsoft 8

The key insight is that each element can extend subsequences ending at value±1. The optimal Dynamic Programming with Hash Map approach tracks count and sum of subsequences ending at each value. Time: O(n), Space: O(k) where k is unique values.

Common Approaches

Approach	Time	Space	Notes
✓ Recursive Memoization	O(n × k)	O(n × k)	Recursively build subsequences with memoization to avoid recomputation
Brute Force - Generate All Subsequences	O(2^n × n)	O(n)	Generate all possible subsequences and check if they are good
Dynamic Programming with Hash Map	O(n)	O(k)	Track count and sum of subsequences ending at each value

Recursive Memoization — Algorithm Steps

Recursive function takes current index and last value in subsequence
Try including current element if it extends subsequence properly
Use memoization to cache results for (index, lastValue) pairs

Visualization

Tap to expand

Step-by-Step Walkthrough

Recursive Call

Try including/excluding each element

Cache Result

Store (index, lastVal) → (count, sum)

Reuse

Return cached results for repeated states

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

#define MOD 1000000007
#define MAX_N 1000

typedef struct {
    long long count;
    long long sum;
} Result;

Result memo[MAX_N][201]; // Assuming values in range [-100, 100]
int memoSet[MAX_N][201];

Result dfs(int* nums, int n, int idx, int lastVal) {
    int memoIdx = lastVal + 100; // Offset for negative values
    
    if (idx == n) {
        Result result = {0, 0};
        return result;
    }
    
    if (memoSet[idx][memoIdx]) {
        return memo[idx][memoIdx];
    }
    
    // Don't include current element
    Result skip = dfs(nums, n, idx + 1, lastVal);
    
    // Include current element if valid
    long long includeCount = 0, includeSum = 0;
    if (lastVal == -101 || abs(nums[idx] - lastVal) == 1) {
        // Single element subsequence
        long long singleSum = nums[idx];
        
        // Extended subsequences
        Result next = dfs(nums, n, idx + 1, nums[idx]);
        
        includeCount = (1 + next.count) % MOD;
        includeSum = (singleSum + next.sum + ((long long) nums[idx] * next.count) % MOD) % MOD;
    }
    
    Result result;
    result.count = (skip.count + includeCount) % MOD;
    result.sum = (skip.sum + includeSum) % MOD;
    
    memo[idx][memoIdx] = result;
    memoSet[idx][memoIdx] = 1;
    return result;
}

int solution(int* nums, int n) {
    memset(memoSet, 0, sizeof(memoSet));
    Result result = dfs(nums, n, 0, -101); // Use -101 as sentinel for no last value
    return result.sum;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    int nums[20];
    int n = 0;
    char* token = strtok(line, "[,]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, "[,]");
    }
    
    printf("%d\n", solution(nums, n));
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

Each (index, value) pair computed once, k unique values

✓ Linear Growth

Space Complexity

O(n × k)

Memoization table stores results for n×k states

⚡ Linearithmic Space

15.4K Views

Medium Frequency

~35 min Avg. Time

284 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Recursive Memoization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler