Watch 10 video solutions for Sum of Consecutive Subsequences, a hard level problem involving Array, Hash Table, Dynamic Programming. This walkthrough by NeetCode has 455,447 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
We call an array arr of length n consecutive if one of the following holds:
arr[i] - arr[i - 1] == 1 for all 1 <= i < n.arr[i] - arr[i - 1] == -1 for all 1 <= i < n.The value of an array is the sum of its elements.
For example, [3, 4, 5] is a consecutive array of value 12 and [9, 8] is another of value 17. While [3, 4, 3] and [8, 6] are not consecutive.
Given an array of integers nums, return the sum of the values of all consecutive non-empty subsequences.
Since the answer may be very large, return it modulo 109 + 7.
Note that an array of length 1 is also considered consecutive.
Example 1:
Input: nums = [1,2]
Output: 6
Explanation:
The consecutive subsequences are: [1], [2], [1, 2].
Example 2:
Input: nums = [1,4,2,3]
Output: 31
Explanation:
The consecutive subsequences are: [1], [4], [2], [3], [1, 2], [2, 3], [4, 3], [1, 2, 3].
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105Problem Overview: You are given an array of integers and need to compute the total sum contributed by all subsequences whose elements form consecutive values (each next value differs by 1). The challenge is counting every valid subsequence efficiently without enumerating all subsets.
Approach 1: Brute Force Subsequence Enumeration (Exponential Time)
The most direct idea is to generate every possible subsequence and check whether the numbers form a consecutive sequence. For each subsequence, sort or validate the difference between adjacent elements and add its contribution to the final sum if valid. This approach requires exploring all 2^n subsequences and performing validation for each, leading to O(2^n * k) time where k is subsequence length, with O(k) auxiliary space for temporary storage. It demonstrates the definition of the problem clearly but becomes infeasible even for moderate input sizes.
Approach 2: Enumeration of Contributions with Hash Map + Dynamic Programming (O(n))
The optimal solution observes that valid subsequences can only extend from a value x-1 to x. Instead of enumerating subsequences explicitly, track how many consecutive subsequences end at each value and what total sum they contribute. Maintain hash tables where each key represents a value v, storing the count and accumulated sum of subsequences ending with v. When processing a number x, look up x-1 in the map. Every subsequence ending at x-1 can extend to x, and you also start a new subsequence containing only x. Update the count and sum for x accordingly and accumulate the contribution to the global answer.
This method effectively performs enumeration of contributions: each element contributes to all subsequences it can extend. Hash lookups and updates are constant time, so scanning the array once yields O(n) time and O(n) space in the worst case. The approach combines ideas from Hash Table lookups and incremental state updates from Dynamic Programming. Since the algorithm processes the array sequentially and tracks states by value, it fits naturally with many Array problems involving subsequence counting.
Recommended for interviews: Interviewers expect the hash-map dynamic programming approach. Brute force shows you understand subsequences and validation rules, but the contribution-based DP demonstrates the key optimization: extend only from x-1 and aggregate counts and sums instead of rebuilding subsequences.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Enumeration | O(2^n * k) | O(k) | Small inputs or when demonstrating the definition of valid subsequences |
| Enumeration of Contributions (Hash Map + DP) | O(n) | O(n) | General case; optimal solution expected in interviews |