Skip to main content
Talentd

Sum of Consecutive Subarrays - Solution & Explanation

MediumPremiumFree on FleetCodeArrayTwo PointersDynamic Programming12 min read
Practice this problem

Problem Statement

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 <= 105
  • 1 <= 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).

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor →

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subarray EnumerationO(n^3)O(1)Conceptual understanding of subarray generation
Prefix Sum OptimizationO(n^2)O(n)When many subarray sum queries are needed
Recurrence / Contribution DPO(n)O(1)Optimal solution for large arrays and interviews

Video Solution

Longest Consecutive Sequence - Leetcode 128 • NeetCode • 904,099 views views

Watch 9 more video solutions →

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).

Ready to solve this problem?

Practice Sum of Consecutive Subarrays with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays