Sum of Consecutive Subarrays solution and explanation
12 more videos on this problem
Subarray Sum Equals K - Prefix Sums - Leetcode 560 - PythonNeetCode · 15:19 · 266K views
Subarray sum equals K | Number of subarrays with sum equals K | Leetcode #560Techdose · 15:44 · 204K views
Minimum Size Subarray Sum - Leetcode 209 - PythonNeetCode · 12:30 · 110K views
LeetCode Subarray Sum Equals K Solution Explained - JavaNick White · 10:08 · 99K views
Continuous Subarray Sum - Leetcode 523 - PythonNeetCode · 14:56 · 82K views
Maximum Sum Circular Subarray - Leetcode 918 - PythonNeetCodeIO · 16:49 · 50K views
Sum of All Odd Length Subarrays | LeetCode 1588 | Explained and Java CodeNate Santti · 15:38 · 34K views
Binary Subarrays with Sum - Leetcode 930 - PythonNeetCodeIO · 9:57 · 22K views
Range Sum of Sorted Subarray Sums - Leetcode 1508 - PythonNeetCodeIO · 16:13 · 14K views
Maximum Absolute Sum of Any Subarray - Leetcode 1749 - PythonNeetCodeIO · 17:18 · 8K views
Subarray Sum Equals K - LeetCode 560 - Coding Interview QuestionsOne Code Man · 10:38 · 6K views
1588. Sum of All Odd Length Subarrays (Leetcode Easy)Programming Live with Larry · 3:02 · 3K views
Binary Subarray with sum | Sliding Window | DSA | Java | Leetcode - 930Think-Twice-Code-Once · 0:33 · 77 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 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] <= 105
Approach overview
Problem 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.
Solution
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).
class Solution:
def getSum(self, nums: List[int]) -> int:
mod = 10**9 + 7
f = g = 1
s = t = nums[0]
ans = nums[0]
for x, y in pairwise(nums):
if y - x == 1:
f += 1
s += f * y
ans = (ans + s) % mod
else:
f = 1
s = y
if y - x == -1:
g += 1
t += g * y
ans = (ans + t) % mod
else:
g = 1
t = y
if abs(y - x) != 1:
ans = (ans + y) % mod
return ansclass Solution {
public int getSum(int[] nums) {
final int mod = (int) 1e9 + 7;
long s = nums[0], t = nums[0], ans = nums[0];
int f = 1, g = 1;
for (int i = 1; i < nums.length; ++i) {
int x = nums[i - 1], y = nums[i];
if (y - x == 1) {
++f;
s += 1L * f * y;
ans = (ans + s) % mod;
} else {
f = 1;
s = y;
}
if (y - x == -1) {
++g;
t += 1L * g * y;
ans = (ans + t) % mod;
} else {
g = 1;
t = y;
}
if (Math.abs(y - x) != 1) {
ans = (ans + y) % mod;
}
}
return (int) ans;
}
}class Solution {
public:
int getSum(vector<int>& nums) {
const int mod = 1e9 + 7;
long long s = nums[0], t = nums[0], ans = nums[0];
int f = 1, g = 1;
for (int i = 1; i < nums.size(); ++i) {
int x = nums[i - 1], y = nums[i];
if (y - x == 1) {
++f;
s += 1LL * f * y;
ans = (ans + s) % mod;
} else {
f = 1;
s = y;
}
if (y - x == -1) {
++g;
t += 1LL * g * y;
ans = (ans + t) % mod;
} else {
g = 1;
t = y;
}
if (abs(y - x) != 1) {
ans = (ans + y) % mod;
}
}
return ans;
}
};function getSum(nums: number[]): number {
const mod = 10 ** 9 + 7;
let f = 1,
g = 1;
let s = nums[0],
t = nums[0];
let ans = nums[0];
for (let i = 1; i < nums.length; i++) {
const x = nums[i - 1];
const y = nums[i];
if (y - x === 1) {
f++;
s += f * y;
ans = (ans + s) % mod;
} else {
f = 1;
s = y;
}
if (y - x === -1) {
g++;
t += g * y;
ans = (ans + t) % mod;
} else {
g = 1;
t = y;
}
if (Math.abs(y - x) !== 1) {
ans = (ans + y) % mod;
}
}
return ans;
}func getSum(nums []int) int {
const mod int = 1e9 + 7
f, g := 1, 1
s, t := nums[0], nums[0]
ans := nums[0]
for i := 1; i < len(nums); i++ {
x, y := nums[i-1], nums[i]
if y-x == 1 {
f++
s += f * y
ans = (ans + s) % mod
} else {
f = 1
s = y
}
if y-x == -1 {
g++
t += g * y
ans = (ans + t) % mod
} else {
g = 1
t = y
}
if abs(y-x) != 1 {
ans = (ans + y) % mod
}
}
return ans
}
func abs(x int) int {
if x < 0 {
return -x
}
return x
}Complexity analysis
| 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 |
Frequently asked questions
Is Sum of Consecutive Subarrays easy or hard?
The problem is typically rated Medium. Generating subarrays is straightforward, but recognizing the contribution or recurrence pattern that reduces the complexity to O(n) requires familiarity with array DP techniques.
Sum of Consecutive Subarrays Python/Java solution
Most implementations follow the recurrence approach. Iterate through the array, maintain the running sum of subarrays ending at the current index, and accumulate it into the final result. The same logic translates directly across Python, Java, C++, Go, and TypeScript.
How to solve Sum of Consecutive Subarrays in O(n)?
Maintain a running value representing the sum of all subarrays ending at the current index. For index i, update endSum using the recurrence endSum = endSum + nums[i] * (i + 1), then add it to the global total. This accumulates contributions without explicitly generating subarrays.
What is the best approach for Sum of Consecutive Subarrays?
The most efficient approach uses a recurrence or contribution-based dynamic programming idea. Each element contributes to multiple subarrays depending on its position. By accumulating the sum of subarrays ending at each index, the total can be computed in O(n) time with O(1) extra space.
Is Sum of Consecutive Subarrays asked at Google/Amazon/Meta?
Subarray sum contribution patterns frequently appear in interviews at companies like Google, Amazon, and Meta. Variants include total subarray sums, subarray minimums, and range contribution problems that rely on similar array reasoning.
What data structure is used in Sum of Consecutive Subarrays?
The problem mainly relies on arrays and arithmetic accumulation. The optimal method uses a dynamic programming style recurrence over the array without requiring additional data structures beyond a few variables.
What is the time complexity of Sum of Consecutive Subarrays?
The optimal solution runs in O(n) time because the array is processed once while maintaining a running contribution value. Brute force enumeration can take O(n^3) time, while prefix sum optimization reduces it to O(n^2).