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 subarrays.
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,3]
Output: 20
Explanation:
The consecutive subarrays are: [1], [2], [3], [1, 2], [2, 3], [1, 2, 3].
Sum of their values would be: 1 + 2 + 3 + 3 + 5 + 6 = 20.
Example 2:
Input: nums = [1,3,5,7]
Output: 16
Explanation:
The consecutive subarrays are: [1], [3], [5], [7].
Sum of their values would be: 1 + 3 + 5 + 7 = 16.
Example 3:
Input: nums = [7,6,1,2]
Output: 32
Explanation:
The consecutive subarrays are: [7], [6], [1], [2], [7, 6], [1, 2].
Sum of their values would be: 7 + 6 + 1 + 2 + 13 + 3 = 32.
Constraints:
1 <= nums.length <= 1051 <= nums[i] <= 105Problem Overview: Given an array, compute the total sum of every possible consecutive subarray. Each contiguous segment contributes its own sum, and the final answer is the accumulation of all those values.
Approach 1: Brute Force Enumeration (Time: O(n^3), Space: O(1))
The most direct method enumerates every possible subarray and computes its sum independently. Use two loops to choose the start and end index, then a third loop to add elements between them. This approach clearly demonstrates how subarrays are formed but quickly becomes impractical because every subarray requires a full traversal to compute its sum. With n elements, there are O(n^2) subarrays and each may take O(n) work, leading to O(n^3) time complexity and constant O(1) space.
Approach 2: Prefix Sum Optimization (Time: O(n^2), Space: O(n))
Precompute a prefix sum array where prefix[i] stores the sum of elements from index 0 to i-1. The sum of any subarray [l, r] can then be calculated in constant time using prefix[r+1] - prefix[l]. Iterate over all possible start and end indices and accumulate their sums using this lookup. The prefix array removes the inner summation loop, reducing the runtime to O(n^2) while using O(n) additional memory. This approach is common in array problems where repeated range-sum queries appear.
Approach 3: Recurrence / Dynamic Contribution (Time: O(n), Space: O(1))
The optimal solution observes how often each element contributes to subarray sums. For an index i, the element nums[i] appears in exactly (i + 1) * (n - i) different subarrays. Instead of generating subarrays explicitly, accumulate the contribution directly. Another equivalent view uses a recurrence: maintain the sum of all subarrays ending at the current index. If endSum represents the total sum of subarrays ending at i-1, then for index i the new value becomes endSum = endSum + nums[i] * (i + 1). Add endSum to the global result each step. This dynamic formulation runs in O(n) time and constant O(1) space, making it ideal for large inputs and aligning with patterns from dynamic programming and cumulative array contributions.
Recommended for interviews: Start with the brute force idea to show you understand how consecutive subarrays are generated. Then transition to the recurrence-based contribution method. Interviewers expect the O(n) dynamic accumulation because it demonstrates pattern recognition with prefix-style reasoning and efficient iteration over the array.
We define two variables f and g, representing the length of the increasing subarray ending at the current element and the length of the decreasing subarray ending at the current element, respectively. We use two other variables s and t to represent the sum of the increasing subarray ending at the current element and the sum of the decreasing subarray ending at the current element, respectively. Initially, f = g = 1, and s = t = nums[0].
Next, we traverse the array starting from the second element. For the current element nums[i], we consider the increasing subarray and the decreasing subarray ending at nums[i].
If nums[i] - nums[i - 1] = 1, then nums[i] can be added to the increasing subarray ending at nums[i - 1]. In this case, we update f and s, and add s to the answer.
If nums[i] - nums[i - 1] = -1, then nums[i] can be added to the decreasing subarray ending at nums[i - 1]. In this case, we update g and t, and add t to the answer.
Otherwise, nums[i] cannot be added to the increasing or decreasing subarray ending at nums[i - 1]. We add nums[i] to the answer.
After the traversal, return the answer.
The time complexity is O(n), where n is the length of the array. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subarray Enumeration | O(n^3) | O(1) | Conceptual understanding of subarray generation |
| Prefix Sum Optimization | O(n^2) | O(n) | When many subarray sum queries are needed |
| Recurrence / Contribution DP | O(n) | O(1) | Optimal solution for large arrays and interviews |
Longest Consecutive Sequence - Leetcode 128 • NeetCode • 904,099 views views
Watch 9 more video solutions →Practice Sum of Consecutive Subarrays with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor