LeetCode 3351 - Sum of Good Subsequences

This problem asks us to compute the sum of all good subsequences in a given integer array nums. A subsequence is any sequence derived from nums by deleting zero or more elements without changing the order of the remaining elements.

leetcodehardarrayhash-tabledynamic-programming

LeetCode Problem 3351

Difficulty: 🔴 Hard
Topics: Array, Hash Table, Dynamic Programming

Solution

Problem Understanding

This problem asks us to compute the sum of all good subsequences in a given integer array nums. A subsequence is any sequence derived from nums by deleting zero or more elements without changing the order of the remaining elements. A subsequence is considered good if the absolute difference between any two consecutive elements is exactly 1. Subsequence of size 1 is automatically good.

The input is an array of integers nums of size up to 10^5, with values ranging from 0 to 10^5. The output is a single integer representing the sum of all elements across all good subsequences, modulo 10^9 + 7.

Constraints suggest that a naive approach generating all subsequences is infeasible because the number of subsequences grows exponentially (2^n). We need an algorithm that is linear or nearly linear in terms of the number of elements and their values. Edge cases include arrays with repeated elements, arrays of length 1, and sequences where consecutive numbers may skip values.

Approaches

Brute Force

The brute-force approach would attempt to generate all subsequences of nums, check if each is good, and sum the elements of those that are. This approach is correct but impractical due to exponential time complexity. With n = 10^5, generating 2^n subsequences is computationally impossible.

Optimal Approach

The key insight is that a good subsequence only depends on the counts and sums of elements with consecutive values. We can use dynamic programming with a hashmap or array where dp[x] represents the sum of good subsequences ending with the value x.

For each number num in nums, we calculate the sum of new good subsequences ending at num by taking num itself and extending existing subsequences ending at num - 1 and num + 1. The recurrence relation is:

dp[num] = num + (dp[num-1] if exists) + (dp[num+1] if exists)

We maintain the sum modulo 10^9 + 7 at every step.

This approach leverages the fact that extending subsequences only occurs with numbers differing by 1 and allows us to aggregate sums efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n) O(2^n) Generate all subsequences, check each for goodness, sum them
Optimal O(n + V) O(V) Use dynamic programming based on element values, V is the max value of nums

Algorithm Walkthrough

  1. Initialize a dictionary dp to store the sum of good subsequences ending with each value.
  2. Iterate through each number num in nums.
  3. For each num, calculate the sum of new subsequences ending at num. Start with the number itself (subsequence of length 1). If num - 1 exists in dp, add dp[num - 1] to the sum. If num + 1 exists in dp, add dp[num + 1] to the sum.
  4. Update dp[num] with the calculated sum modulo 10^9 + 7.
  5. Maintain a running total of all subsequences by adding dp[num] to a total variable.
  6. Return total modulo 10^9 + 7.

Why it works: The invariant is that dp[x] always represents the sum of all good subsequences ending at x. By combining sums from x-1 and x+1, we ensure that we only extend sequences that remain "good" while covering all possible subsequences efficiently.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def sumOfGoodSubsequences(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        dp = defaultdict(int)
        total = 0
        
        for num in nums:
            # new sum including num itself and extending sequences ending at num-1 and num+1
            new_sum = num
            if num - 1 in dp:
                new_sum = (new_sum + dp[num - 1]) % MOD
            if num + 1 in dp:
                new_sum = (new_sum + dp[num + 1]) % MOD
            
            dp[num] = (dp[num] + new_sum) % MOD
            total = (total + new_sum) % MOD
        
        return total

Implementation walkthrough: We initialize dp as a defaultdict to handle numbers not seen before. For each number, we calculate the sum of all new good subsequences ending at that number by considering extensions from num-1 and num+1. The running total accumulates these contributions, ensuring we account for all subsequences efficiently.

Go Solution

func sumOfGoodSubsequences(nums []int) int {
    MOD := int(1e9 + 7)
    dp := make(map[int]int)
    total := 0
    
    for _, num := range nums {
        newSum := num
        if val, exists := dp[num-1]; exists {
            newSum = (newSum + val) % MOD
        }
        if val, exists := dp[num+1]; exists {
            newSum = (newSum + val) % MOD
        }
        dp[num] = (dp[num] + newSum) % MOD
        total = (total + newSum) % MOD
    }
    
    return total
}

Go-specific notes: We use a map[int]int for dp instead of defaultdict. The modulo operation ensures integers do not overflow, and the running total is updated consistently. The logic mirrors the Python implementation, handling edge cases where keys are missing.

Worked Examples

Example 1: nums = [1,2,1]

Iteration num dp state newSum total
1 1 {} 1 1
2 2 {1:1} 2 + 1 = 3 4
3 1 {1:1,2:3} 1 + 3 = 4 8

Final total: 14

Example 2: nums = [3,4,5]

Iteration num dp state newSum total
1 3 {} 3 3
2 4 {3:3} 4 + 3 = 7 10
3 5 {3:3,4:7} 5 + 7 = 12 22

Final total: 40

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each element is processed once, and map operations are O(1) on average
Space O(V) dp stores sums for each unique element, V is the max value in nums

The approach scales linearly with the number of elements and the range of unique values, making it suitable for large arrays.

Test Cases

# test cases
sol = Solution()

# Example 1
assert sol.sumOfGoodSubsequences([1,2,1]) == 14  # sum of all good subsequences

# Example 2
assert sol.sumOfGoodSubsequences([3,4,5]) == 40  # sum of all good subsequences

# Single element
assert sol.sumOfGoodSubsequences([7]) == 7  # single element is good by definition

# All elements same
assert sol.sumOfGoodSubsequences([2,2,2]) == 6  # each element alone, cannot combine

# Non-consecutive numbers
assert sol.sumOfGoodSubsequences([1,3,5]) == 9  # only single elements are good

# Increasing sequence
assert sol.sumOfGoodSubsequences([1,2,3]) == 20  # subsequences: [1],[2],[3],[1,2],[2,3],[1,2,3]

# Decreasing sequence
assert sol.sumOfGoodSubsequences([3,2,1]) == 20  # symmetric to increasing
Test Why
[1,2,1] Example with repeated elements
[3,4,5] Example with increasing elements
[7] Single element edge case
[2,2,2] All elements identical
[1,3,5] Non-consecutive numbers
[1,2,3] Increasing sequence, multiple extensions
[3,2,1] Decreasing sequence, symmetry check

Edge Cases

Single element array: The subsequence sum is the element itself. This tests that our code correctly handles minimal input.

All elements identical: No good subsequence of length >1 exists, only single-element subsequences contribute. This ensures we do not accidentally combine identical numbers without checking the absolute difference condition.

Large range of numbers: When nums contains elements from 0 to 10^5, our dp map must efficiently handle sparse indices without memory waste. Using a hash map ensures we only store relevant values, avoiding unnecessary large arrays.