Sum of Consecutive Subarrays

Problem

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.

Examples

Example 1:

1
2
3
4
5
6


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:

1
2
3
4
5


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:

1
2
3
4
5


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 <= 10^5
1 <= nums[i] <= 10^5

Solution

Method 1 – Two Pointers and Prefix Sums

Intuition

For each possible start of a subarray, extend the subarray as long as the difference between consecutive elements is +1 or -1. Use prefix sums to quickly compute the sum of each valid subarray.

Approach

Compute prefix sums for the array.
For each index, treat it as the start of a subarray and use two pointers to find the longest consecutive subarray (increasing or decreasing).
For each valid subarray, add its sum to the answer.
Since each subarray is processed once, the total time is linear.
Return the answer modulo 10^9 + 7.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
public:
    int sumOfConsecutiveSubarrays(vector<int>& nums) {
        int n = nums.size(), mod = 1e9 + 7;
        vector<long long> pre(n+1);
        for (int i = 0; i < n; ++i) pre[i+1] = pre[i] + nums[i];
        long long ans = 0;
        for (int i = 0; i < n; ++i) {
            // Increasing
            int j = i;
            while (j+1 < n && nums[j+1] - nums[j] == 1) ++j;
            for (int k = i; k <= j; ++k) ans = (ans + pre[k+1] - pre[i]) % mod;
            i = j;
        }
        for (int i = 0; i < n; ++i) {
            // Decreasing
            int j = i;
            while (j+1 < n && nums[j+1] - nums[j] == -1) ++j;
            if (j > i) {
                for (int k = i+1; k <= j; ++k) ans = (ans + pre[k+1] - pre[i]) % mod;
            }
            i = j;
        }
        return (int)ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33


func sumOfConsecutiveSubarrays(nums []int) int {
    n, mod := len(nums), int(1e9+7)
    pre := make([]int, n+1)
    for i := 0; i < n; i++ {
        pre[i+1] = pre[i] + nums[i]
    }
    ans := 0
    i := 0
    for i < n {
        j := i
        for j+1 < n && nums[j+1]-nums[j] == 1 {
            j++
        }
        for k := i; k <= j; k++ {
            ans = (ans + pre[k+1] - pre[i]) % mod
        }
        i = j + 1
    }
    i = 0
    for i < n {
        j := i
        for j+1 < n && nums[j+1]-nums[j] == -1 {
            j++
        }
        if j > i {
            for k := i+1; k <= j; k++ {
                ans = (ans + pre[k+1] - pre[i]) % mod
            }
        }
        i = j + 1
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23


class Solution {
    public int sumOfConsecutiveSubarrays(int[] nums) {
        int n = nums.length, mod = 1_000_000_007;
        long[] pre = new long[n+1];
        for (int i = 0; i < n; i++) pre[i+1] = pre[i] + nums[i];
        long ans = 0;
        for (int i = 0; i < n; ) {
            int j = i;
            while (j+1 < n && nums[j+1] - nums[j] == 1) j++;
            for (int k = i; k <= j; k++) ans = (ans + pre[k+1] - pre[i]) % mod;
            i = j + 1;
        }
        for (int i = 0; i < n; ) {
            int j = i;
            while (j+1 < n && nums[j+1] - nums[j] == -1) j++;
            if (j > i) {
                for (int k = i+1; k <= j; k++) ans = (ans + pre[k+1] - pre[i]) % mod;
            }
            i = j + 1;
        }
        return (int)ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution {
    fun sumOfConsecutiveSubarrays(nums: IntArray): Int {
        val n = nums.size
        val mod = 1_000_000_007
        val pre = LongArray(n+1)
        for (i in 0 until n) pre[i+1] = pre[i] + nums[i]
        var ans = 0L
        var i = 0
        while (i < n) {
            var j = i
            while (j+1 < n && nums[j+1] - nums[j] == 1) j++
            for (k in i..j) ans = (ans + pre[k+1] - pre[i]) % mod
            i = j + 1
        }
        i = 0
        while (i < n) {
            var j = i
            while (j+1 < n && nums[j+1] - nums[j] == -1) j++
            if (j > i) {
                for (k in i+1..j) ans = (ans + pre[k+1] - pre[i]) % mod
            }
            i = j + 1
        }
        return ans.toInt()
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26


class Solution:
    def sumOfConsecutiveSubarrays(self, nums: list[int]) -> int:
        mod = 10 ** 9 + 7
        n = len(nums)
        pre = [0] * (n + 1)
        for i in range(n):
            pre[i+1] = pre[i] + nums[i]
        ans = 0
        i = 0
        while i < n:
            j = i
            while j+1 < n and nums[j+1] - nums[j] == 1:
                j += 1
            for k in range(i, j+1):
                ans = (ans + pre[k+1] - pre[i]) % mod
            i = j + 1
        i = 0
        while i < n:
            j = i
            while j+1 < n and nums[j+1] - nums[j] == -1:
                j += 1
            if j > i:
                for k in range(i+1, j+1):
                    ans = (ans + pre[k+1] - pre[i]) % mod
            i = j + 1
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32


impl Solution {
    pub fn sum_of_consecutive_subarrays(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let modn = 1_000_000_007i64;
        let mut pre = vec![0i64; n+1];
        for i in 0..n {
            pre[i+1] = pre[i] + nums[i] as i64;
        }
        let mut ans = 0i64;
        let mut i = 0;
        while i < n {
            let mut j = i;
            while j+1 < n && nums[j+1] - nums[j] == 1 { j += 1; }
            for k in i..=j {
                ans = (ans + pre[k+1] - pre[i]) % modn;
            }
            i = j + 1;
        }
        i = 0;
        while i < n {
            let mut j = i;
            while j+1 < n && nums[j+1] - nums[j] == -1 { j += 1; }
            if j > i {
                for k in i+1..=j {
                    ans = (ans + pre[k+1] - pre[i]) % modn;
                }
            }
            i = j + 1;
        }
        ans as i32
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25


class Solution {
    sumOfConsecutiveSubarrays(nums: number[]): number {
        const n = nums.length, mod = 1e9 + 7;
        const pre = new Array(n+1).fill(0);
        for (let i = 0; i < n; i++) pre[i+1] = pre[i] + nums[i];
        let ans = 0;
        let i = 0;
        while (i < n) {
            let j = i;
            while (j+1 < n && nums[j+1] - nums[j] === 1) j++;
            for (let k = i; k <= j; k++) ans = (ans + pre[k+1] - pre[i]) % mod;
            i = j + 1;
        }
        i = 0;
        while (i < n) {
            let j = i;
            while (j+1 < n && nums[j+1] - nums[j] === -1) j++;
            if (j > i) {
                for (let k = i+1; k <= j; k++) ans = (ans + pre[k+1] - pre[i]) % mod;
            }
            i = j + 1;
        }
        return ans;
    }
}

Complexity

⏰ Time complexity: O(n) — Each subarray is processed once using two pointers and prefix sums.
🧺 Space complexity: O(n) — For the prefix sum array.

Problem#

Examples#

Solution#

Method 1 – Two Pointers and Prefix Sums#

Intuition#

Approach#

Code#

Complexity#