3284. Sum of Consecutive Subarrays 🔒

Description

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

Solutions

Solution 1: Recurrence

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 = \textit{nums}[0]\).

Next, we traverse the array starting from the second element. For the current element \(\textit{nums}[i]\), we consider the increasing subarray and the decreasing subarray ending at \(\textit{nums}[i]\).

If \(\textit{nums}[i] - \textit{nums}[i - 1] = 1\), then \(\textit{nums}[i]\) can be added to the increasing subarray ending at \(\textit{nums}[i - 1]\). In this case, we update \(f\) and \(s\), and add \(s\) to the answer.

If \(\textit{nums}[i] - \textit{nums}[i - 1] = -1\), then \(\textit{nums}[i]\) can be added to the decreasing subarray ending at \(\textit{nums}[i - 1]\). In this case, we update \(g\) and \(t\), and add \(t\) to the answer.

Otherwise, \(\textit{nums}[i]\) cannot be added to the increasing or decreasing subarray ending at \(\textit{nums}[i - 1]\). We add \(\textit{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)\).

Python3JavaC++GoTypeScript

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 ans

class 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;
    }
};

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
}

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;
}

3284. Sum of Consecutive Subarrays 🔒

Description

Solutions

Solution 1: Recurrence

Comments