Sum of Consecutive Subsequences solution and explanation
13 more videos on this problem
Leetcode 1498 - Number of Subsequences That Satisfy the Given Sum Condition - PythonNeetCode · 8:52 · 32K views
Arrays | Leetcode 659 | Split Array Into Consecutive SubsequencesNideesh Terapalli · 16:20 · 20K views
LeetCode 659. Split Array into Consecutive Subsequences v1Happy Coding · 13:12 · 11K views
Number of Subsequences That Satisfy the Given Sum Condition (LeetCode)Jyotinder Singh · 12:24 · 4K views
3351. Sum of Good Subsequences | DP | Don't Overthink here :)Aryan Mittal · 14:38 · 3K views
LeetCode 659. Split Array into Consecutive Subsequences v2Happy Coding · 16:24 · 1K views
829. Consecutive Numbers Sum (LeetCode)hakunamatasq · 5:28 · 1K views
1498. Number of Subsequences That Satisfy the Given Sum Condition | LeetCode Daily Challenge | POTDDeepCodes · 17:51 · 1K views
LeetCode 1498. Number of Subsequences That Satisfy the Given Sum ConditionHappy Coding · 17:59 · 1K views
Number of Subsequences That Satisfy the Given Sum Condition - Leetcode 1498 - PythonTechError · 5:22 · 981 views
1498. Number of Subsequences That Satisfy the Given Sum Condition (Leetcode Medium)Programming Live with Larry · 5:27 · 863 views
Leetcode 659: Split Array into Consecutive SubsequencesAlgorithms Casts · 15:39 · 481 views
Leetcode 659. Split Array into Consecutive SubsequencesElite Code · 36:29 · 338 views
Number of Subsequences That Satisfy the Given Sum Condition - LeetCode 1498 - Python SolutionCode with Carter · 6:08 · 315 views
The problem
We call an array arr of length n consecutive if one of the following holds:
arr[i] - arr[i - 1] == 1for all1 <= i < n.arr[i] - arr[i - 1] == -1for all1 <= 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] <= 105
Approach overview
Problem 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.
Solution
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.
class Solution:
def getSum(self, nums: List[int]) -> int:
def calc(nums: List[int]) -> int:
n = len(nums)
left = [0] * n
right = [0] * n
cnt = Counter()
for i in range(1, n):
cnt[nums[i - 1]] += 1 + cnt[nums[i - 1] - 1]
left[i] = cnt[nums[i] - 1]
cnt = Counter()
for i in range(n - 2, -1, -1):
cnt[nums[i + 1]] += 1 + cnt[nums[i + 1] + 1]
right[i] = cnt[nums[i] + 1]
return sum((l + r + l * r) * x for l, r, x in zip(left, right, nums)) % mod
mod = 10**9 + 7
x = calc(nums)
nums.reverse()
y = calc(nums)
return (x + y + sum(nums)) % modclass Solution {
private final int mod = (int) 1e9 + 7;
public int getSum(int[] nums) {
long x = calc(nums);
for (int i = 0, j = nums.length - 1; i < j; ++i, --j) {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
}
long y = calc(nums);
long s = Arrays.stream(nums).asLongStream().sum();
return (int) ((x + y + s) % mod);
}
private long calc(int[] nums) {
int n = nums.length;
long[] left = new long[n];
long[] right = new long[n];
Map<Integer, Long> cnt = new HashMap<>();
for (int i = 1; i < n; ++i) {
cnt.merge(nums[i - 1], 1 + cnt.getOrDefault(nums[i - 1] - 1, 0L), Long::sum);
left[i] = cnt.getOrDefault(nums[i] - 1, 0L);
}
cnt.clear();
for (int i = n - 2; i >= 0; --i) {
cnt.merge(nums[i + 1], 1 + cnt.getOrDefault(nums[i + 1] + 1, 0L), Long::sum);
right[i] = cnt.getOrDefault(nums[i] + 1, 0L);
}
long ans = 0;
for (int i = 0; i < n; ++i) {
ans = (ans + (left[i] + right[i] + left[i] * right[i] % mod) * nums[i] % mod) % mod;
}
return ans;
}
}class Solution {
public:
int getSum(vector<int>& nums) {
using ll = long long;
const int mod = 1e9 + 7;
auto calc = [&](const vector<int>& nums) -> ll {
int n = nums.size();
vector<ll> left(n), right(n);
unordered_map<int, ll> cnt;
for (int i = 1; i < n; ++i) {
cnt[nums[i - 1]] += 1 + cnt[nums[i - 1] - 1];
left[i] = cnt[nums[i] - 1];
}
cnt.clear();
for (int i = n - 2; i >= 0; --i) {
cnt[nums[i + 1]] += 1 + cnt[nums[i + 1] + 1];
right[i] = cnt[nums[i] + 1];
}
ll ans = 0;
for (int i = 0; i < n; ++i) {
ans = (ans + (left[i] + right[i] + left[i] * right[i] % mod) * nums[i] % mod) % mod;
}
return ans;
};
ll x = calc(nums);
reverse(nums.begin(), nums.end());
ll y = calc(nums);
ll s = accumulate(nums.begin(), nums.end(), 0LL);
return static_cast<int>((x + y + s) % mod);
}
};func getSum(nums []int) int {
const mod = 1e9 + 7
calc := func(nums []int) int64 {
n := len(nums)
left := make([]int64, n)
right := make([]int64, n)
cnt := make(map[int]int64)
for i := 1; i < n; i++ {
cnt[nums[i-1]] += 1 + cnt[nums[i-1]-1]
left[i] = cnt[nums[i]-1]
}
cnt = make(map[int]int64)
for i := n - 2; i >= 0; i-- {
cnt[nums[i+1]] += 1 + cnt[nums[i+1]+1]
right[i] = cnt[nums[i]+1]
}
var ans int64
for i, x := range nums {
ans = (ans + (left[i]+right[i]+(left[i]*right[i]%mod))*int64(x)%mod) % mod
}
return ans
}
x := calc(nums)
for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 {
nums[i], nums[j] = nums[j], nums[i]
}
y := calc(nums)
s := int64(0)
for _, num := range nums {
s += int64(num)
}
return int((x + y + s) % mod)
}Complexity analysis
| 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 |
Frequently asked questions
Is Sum of Consecutive Subsequences easy or hard?
The problem is considered Hard because it requires recognizing the contribution pattern and designing a dynamic programming state keyed by values. A brute-force subsequence approach is straightforward but exponential, while the optimal O(n) solution requires deeper insight.
Sum of Consecutive Subsequences Python/Java solution
Typical implementations use a dictionary or HashMap to store counts and sums of subsequences ending at each value. The algorithm iterates through the array once, updates states using x and x-1 relationships, and accumulates the total contribution. The same logic works across Python, Java, C++, and Go.
How to solve Sum of Consecutive Subsequences in O(n)?
Maintain a hash map that stores the count and cumulative sum of subsequences ending at each value. For every element x in the array, check if x-1 exists in the map and extend those subsequences. Add the contribution of x to the new subsequences and update the state for x. This single-pass dynamic programming approach achieves O(n) complexity.
What is the best approach for Sum of Consecutive Subsequences?
The most efficient approach uses a hash table combined with dynamic programming. Track the number of valid subsequences and their total sum ending at each value. When processing value x, extend all subsequences ending at x-1 and also start a new subsequence with x. This contribution-based method runs in O(n) time with O(n) space.
Is Sum of Consecutive Subsequences asked at Google/Amazon/Meta?
Problems combining hash tables with dynamic programming over subsequences frequently appear in interviews at companies like Google, Amazon, and Meta. Variants of consecutive subsequence counting and contribution-based DP are common interview patterns.
What data structure is used in Sum of Consecutive Subsequences?
The core data structure is a hash table (or unordered map) that stores dynamic programming states indexed by value. It allows constant-time lookup of subsequences ending at value x-1 so they can be extended to x.
What is the time complexity of Sum of Consecutive Subsequences?
The optimal solution runs in O(n) time because each element is processed once and only constant-time hash map lookups and updates are performed. Space complexity is O(n) in the worst case to store dynamic programming states for distinct values.