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.

Description Hints 6 Solution Video 8:52

3299. Sum of Consecutive Subsequences

Hard44.1% acceptancePremium elsewhere, free here

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 10⁹+ 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 <= 10⁵
1 <= nums[i] <= 10⁵

Topics

Hints open one at a time

Hint 1

Try to count the number of times each element occurred in a consecutive subsequence, then you can find the answer easily.

Hint 2

Think of dynamic programming as a solution to calculate the number in the previous hint.

Hint 3

Let left_inc[i] be the number of increasing consecutive subsequences ending at nums[i] (except for nums[i] itself).

Hint 4

Let right_inc[i] be the number of increasing consecutive subsequences starting at nums[i] (except for nums[i] itself).

Hint 5

Then nums[i] is in left_inc[i] + right_inc[i] + left_inc[i] * right_inc[i] + 1 increasing subsequences.

Hint 6

Do the same for decreasing consecutive subsequences.

8:52

Still stuck?Read the written solution, or watch a walkthrough.

Open solution

LanguageLoading editor…

1class Solution:
  def solve(self):
      pass


Starter codePython 3Spaces: 4

Examples

Case 1Case 2

Input

[1,2]

Input

[1,4,2,3]

Your code is saved on this device.Solution