LeetCode 3299 - Sum of Consecutive Subsequences

We are given an array nums, and we must consider all non-empty subsequences of that array. A subsequence preserves the original order of elements, but elements do not need to be contiguous.

leetcodehardarrayhash-tabledynamic-programming

LeetCode Problem 3299

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

Solution

LeetCode 3299 - Sum of Consecutive Subsequences

Problem Understanding

We are given an array nums, and we must consider all non-empty subsequences of that array.

A subsequence preserves the original order of elements, but elements do not need to be contiguous.

A subsequence is considered consecutive if every adjacent pair differs by exactly +1 or exactly -1 throughout the entire subsequence.

For example:

  • [1, 2, 3] is consecutive because every step is +1.
  • [5, 4, 3] is consecutive because every step is -1.
  • [1, 2, 1] is not consecutive because the differences are +1 and -1.
  • [8, 6] is not consecutive because the difference is -2.

The value of a subsequence is simply the sum of its elements.

Our task is to compute the sum of the values of every consecutive non-empty subsequence and return the result modulo 10^9 + 7.

The constraints are important:

  • n can be as large as 100,000.
  • Values can be as large as 100,000.

Because the number of subsequences is exponential, it is impossible to enumerate all subsequences directly.

Some important observations:

  • Every single element forms a valid consecutive subsequence.
  • A valid subsequence of length greater than one must be entirely increasing by 1 at every step or entirely decreasing by 1 at every step.
  • The same subsequence cannot be both increasing and decreasing unless its length is 1.

These observations lead directly to an efficient dynamic programming solution.

Approaches

Brute Force

The most direct approach is to generate every subsequence.

For each subsequence:

  1. Check whether all adjacent differences are +1.
  2. Check whether all adjacent differences are -1.
  3. If either condition holds, add the subsequence sum to the answer.

This approach is correct because it explicitly examines every possible subsequence.

Unfortunately, an array of length n has 2^n subsequences. Even for n = 50, this becomes completely infeasible, and the actual constraint is 100,000.

Therefore, a brute-force solution cannot be used.

Key Insight

A consecutive subsequence is completely determined by its last value and whether it is:

  • increasing by 1, or
  • decreasing by 1.

Suppose we process the array from left to right.

When we encounter a value x:

  • Any increasing consecutive subsequence ending with value x - 1 can be extended by appending x.
  • Any decreasing consecutive subsequence ending with value x + 1 can be extended by appending x.

This suggests maintaining dynamic programming states indexed by value.

Instead of storing actual subsequences, we store:

  • how many valid subsequences end with a particular value,
  • the total sum of values of those subsequences.

Using these aggregate statistics allows us to extend all relevant subsequences in constant time.

Approach Comparison

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n · n) O(n) Enumerates all subsequences
Optimal DP + Hash Maps O(n) O(U) Tracks counts and sums by ending value

Here U is the number of distinct values encountered.

Algorithm Walkthrough

State Definition

Maintain four hash maps:

  • inc_count[v] = number of increasing consecutive subsequences ending with value v
  • inc_sum[v] = total value sum of those increasing subsequences
  • dec_count[v] = number of decreasing consecutive subsequences ending with value v
  • dec_sum[v] = total value sum of those decreasing subsequences

Processing a Value x

For increasing subsequences:

We can create:

  1. The singleton subsequence [x].
  2. Any increasing subsequence ending with x - 1, extended by x.

Therefore:

new_inc_count = 1 + inc_count[x - 1]

For sums:

  • Singleton contributes x.
  • Every extended subsequence gains an additional x.

So:

new_inc_sum =
    x
    + inc_sum[x - 1]
    + inc_count[x - 1] * x

Decreasing Subsequences

Similarly:

new_dec_count = 1 + dec_count[x + 1]

and

new_dec_sum =
    x
    + dec_sum[x + 1]
    + dec_count[x + 1] * x

Add Contributions

Every increasing subsequence ending at the current position contributes through new_inc_sum.

Every decreasing subsequence ending at the current position contributes through new_dec_sum.

However, the singleton [x] appears in both groups.

Therefore:

answer += new_inc_sum + new_dec_sum - x

The subtraction removes the duplicate singleton contribution.

Update DP Tables

Store the newly created subsequences:

inc_count[x] += new_inc_count
inc_sum[x] += new_inc_sum

dec_count[x] += new_dec_count
dec_sum[x] += new_dec_sum

Why it Works

The key invariant is that after processing a prefix of the array:

  • inc_count[v] and inc_sum[v] represent all increasing consecutive subsequences ending with value v.
  • dec_count[v] and dec_sum[v] represent all decreasing consecutive subsequences ending with value v.

When a new value x is processed, every valid subsequence that can legally extend to x must end with x - 1 for increasing sequences or x + 1 for decreasing sequences. The recurrence enumerates exactly those possibilities and no others.

Thus every valid consecutive subsequence is counted exactly once, except singletons which are counted once in each direction and corrected by subtracting x.

Python Solution

from typing import List
from collections import defaultdict

class Solution:
    def getSum(self, nums: List[int]) -> int:
        MOD = 10**9 + 7

        inc_count = defaultdict(int)
        inc_sum = defaultdict(int)

        dec_count = defaultdict(int)
        dec_sum = defaultdict(int)

        answer = 0

        for x in nums:
            prev_inc_count = inc_count[x - 1]
            prev_inc_sum = inc_sum[x - 1]

            new_inc_count = (1 + prev_inc_count) % MOD
            new_inc_sum = (
                x
                + prev_inc_sum
                + prev_inc_count * x
            ) % MOD

            prev_dec_count = dec_count[x + 1]
            prev_dec_sum = dec_sum[x + 1]

            new_dec_count = (1 + prev_dec_count) % MOD
            new_dec_sum = (
                x
                + prev_dec_sum
                + prev_dec_count * x
            ) % MOD

            answer = (
                answer
                + new_inc_sum
                + new_dec_sum
                - x
            ) % MOD

            inc_count[x] = (inc_count[x] + new_inc_count) % MOD
            inc_sum[x] = (inc_sum[x] + new_inc_sum) % MOD

            dec_count[x] = (dec_count[x] + new_dec_count) % MOD
            dec_sum[x] = (dec_sum[x] + new_dec_sum) % MOD

        return answer % MOD

The implementation directly follows the dynamic programming formulation.

The four hash maps store counts and value sums for increasing and decreasing subsequences separately.

For each number x, we first compute all new increasing subsequences by extending subsequences ending with x - 1. We then compute all new decreasing subsequences by extending subsequences ending with x + 1.

The newly formed subsequences contribute to the final answer immediately. Because singleton subsequences are included in both directions, we subtract x once to avoid double counting.

Finally, the DP tables are updated so future elements can extend these newly created subsequences.

Go Solution

func getSum(nums []int) int {
	const MOD int64 = 1000000007

	incCount := map[int]int64{}
	incSum := map[int]int64{}

	decCount := map[int]int64{}
	decSum := map[int]int64{}

	var answer int64 = 0

	for _, x := range nums {
		v := int64(x)

		prevIncCount := incCount[x-1]
		prevIncSum := incSum[x-1]

		newIncCount := (1 + prevIncCount) % MOD
		newIncSum := (v + prevIncSum + prevIncCount*v) % MOD

		prevDecCount := decCount[x+1]
		prevDecSum := decSum[x+1]

		newDecCount := (1 + prevDecCount) % MOD
		newDecSum := (v + prevDecSum + prevDecCount*v) % MOD

		answer = (answer + newIncSum + newDecSum - v) % MOD
		if answer < 0 {
			answer += MOD
		}

		incCount[x] = (incCount[x] + newIncCount) % MOD
		incSum[x] = (incSum[x] + newIncSum) % MOD

		decCount[x] = (decCount[x] + newDecCount) % MOD
		decSum[x] = (decSum[x] + newDecSum) % MOD
	}

	return int(answer)
}

The Go version uses map[int]int64 instead of Python dictionaries.

All arithmetic is performed using int64 because the intermediate values can become very large before taking the modulo. Go maps return the zero value for missing keys, which naturally matches the DP recurrence.

Worked Examples

Example 1

nums = [1, 2]

Processing 1

Variable Value
new_inc_count 1
new_inc_sum 1
new_dec_count 1
new_dec_sum 1
answer 1

DP state:

Map Content
inc_count {1: 1}
inc_sum {1: 1}
dec_count {1: 1}
dec_sum {1: 1}

Processing 2

Increasing extensions come from value 1.

Variable Value
prev_inc_count 1
prev_inc_sum 1
new_inc_sum 5

The increasing subsequences are:

[2]      -> 2
[1,2]    -> 3

Total = 5.

No decreasing extension exists.

Variable Value
new_dec_sum 2

Answer update:

answer += 5 + 2 - 2

Final answer:

6

Example 2

nums = [1, 4, 2, 3]

After processing 1

Answer = 1

After processing 4

Answer = 5

Current valid subsequences:

[1]
[4]

After processing 2

Increasing extension from value 1:

[2]
[1,2]

Contribution:

2 + 3 = 5

Answer becomes:

10

After processing 3

Increasing extension from value 2:

[3]
[2,3]
[1,2,3]

Contribution:

3 + 5 + 6 = 14

Decreasing extension from value 4:

[4,3]

Contribution:

7

Total added:

14 + 10 - 3 = 21

Final answer:

31

Matching the expected output.

Complexity Analysis

Measure Complexity Explanation
Time O(n) Constant amount of work per element
Space O(U) Hash maps store information for distinct values

The algorithm processes each array element exactly once. Every lookup and update in the hash maps is expected O(1), so the total running time is linear in the size of the input. The space usage is proportional to the number of distinct values that appear.

Test Cases

sol = Solution()

assert sol.getSum([1, 2]) == 6          # example 1
assert sol.getSum([1, 4, 2, 3]) == 31   # example 2

assert sol.getSum([5]) == 5             # single element

assert sol.getSum([1, 3, 5]) == 9       # only singletons

assert sol.getSum([3, 2, 1]) == 20      # decreasing chain

assert sol.getSum([1, 2, 3]) == 20      # increasing chain

assert sol.getSum([1, 1]) == 4          # duplicate values

assert sol.getSum([1, 2, 1]) == 10      # mixed directions

assert sol.getSum([2, 2, 2]) == 6       # all equal

assert sol.getSum([1, 2, 2, 3]) == 32   # duplicate middle value

assert sol.getSum([100000]) == 100000   # maximum value boundary

Test Summary

Test Why
[1,2] Smallest non-trivial increasing case
[1,4,2,3] Official example with both directions
[5] Single-element subsequence
[1,3,5] No extensions possible
[3,2,1] Pure decreasing chain
[1,2,3] Pure increasing chain
[1,1] Duplicate values
[1,2,1] Direction changes in the array
[2,2,2] All elements identical
[1,2,2,3] Multiple ways to extend through duplicates
[100000] Maximum value boundary

Edge Cases

Single Element Array

When the array contains only one element, the only valid subsequence is the element itself. A common mistake is to focus exclusively on extension logic and forget that every element creates a singleton subsequence. The recurrence explicitly includes the singleton through the +1 count and the +x sum contribution.

Duplicate Values

Values such as [1,1,1] cannot extend one another because consecutive subsequences require a difference of exactly 1 or -1. The algorithm only looks up x-1 and x+1, so equal values never create invalid extensions.

Multiple Occurrences of the Same Number

Consider [1,2,1,2]. Different positions can generate different subsequences ending with the same value. Storing only one state per value would lose information. The solution accumulates counts and sums for all subsequences ending with a particular value, ensuring every valid subsequence remains available for future extensions.

Large Inputs

The number of valid subsequences can be enormous, far exceeding standard integer limits. The implementation performs all updates modulo 10^9 + 7, preventing overflow and satisfying the problem requirements.