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.
Let us count how many times each element nums[i] appears in a continuous subsequence of length greater than 1. Then, multiplying this count by nums[i] gives the contribution of nums[i] in all continuous subsequences of length greater than 1. We sum these contributions, and adding the sum of all elements, we get the answer.
We can first compute the contribution of strictly increasing subsequences, then the contribution of strictly decreasing subsequences, and finally add the sum of all elements.
To implement this, we define a function calc(nums), where nums is an array. This function returns the sum of all continuous subsequences of length greater than 1 in nums.
In the function, we can use two arrays, left and right, to record the number of strictly increasing subsequences ending with nums[i] - 1 on the left of each element nums[i], and the number of strictly increasing subsequences starting with nums[i] + 1 on the right of each element nums[i]. In this way, we can calculate the contribution of nums in all continuous subsequences of length greater than 1 in O(n) time complexity.
In the main function, we first call calc(nums) to compute the contribution of strictly increasing subsequences, then reverse nums and call calc(nums) again to compute the contribution of strictly decreasing subsequences. Finally, adding the sum of all elements gives the answer.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array nums.
| 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 |
Leetcode 128 - LONGEST CONSECUTIVE SEQUENCE • NeetCode • 455,447 views views
Watch 9 more video solutions →Practice Sum of Consecutive Subsequences with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor