LeetCode 3284 - Sum of Consecutive Subarrays

The problem asks us to compute the sum of all consecutive subarrays in a given integer array nums. A consecutive subarray is defined as one where each element differs from the previous by exactly 1 or -1.

leetcodemediumarraytwo-pointersdynamic-programming

LeetCode Problem 3284

Difficulty: 🟡 Medium
Topics: Array, Two Pointers, Dynamic Programming

Solution

Problem Understanding

The problem asks us to compute the sum of all consecutive subarrays in a given integer array nums. A consecutive subarray is defined as one where each element differs from the previous by exactly 1 or -1. This means the sequence can strictly increase or strictly decrease by 1 at each step. Subarrays of length 1 are automatically consecutive.

The input is an array of integers of length up to $10^5$, and each integer is at most $10^5$. The output is the sum of all elements in all consecutive subarrays, modulo $10^9 + 7$.

Important observations include that a naive approach iterating over all possible subarrays would be too slow for the input size, and that the key is to efficiently identify consecutive segments and compute their contributions. Edge cases include arrays of length 1, arrays with all identical elements, arrays with alternating increases and decreases, and arrays with large numbers that require modulo handling.

Approaches

A brute-force approach would iterate over all possible subarrays and check if each subarray is consecutive. For each consecutive subarray, we would calculate its sum and add it to the result. This approach is correct but has time complexity $O(n^2)$ for checking all subarrays and $O(n^3)$ if you sum elements naively, which is infeasible for $n$ up to $10^5$.

The key insight for a better solution is that consecutive subarrays form contiguous increasing or decreasing segments. Once a segment is identified, we can compute the sum of all consecutive subarrays in that segment in $O(k)$ time by maintaining a running sum of the segment elements. Specifically, for each element in a segment, the number of subarrays ending at that element can be determined and used to update the cumulative sum efficiently.

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(1) Check all subarrays and sum if consecutive
Optimal O(n) O(1) Use a sliding window to accumulate consecutive subarray sums efficiently

Algorithm Walkthrough

  1. Initialize a variable total_sum to 0 to hold the final answer and a current_sum to track the sum of consecutive subarrays ending at the current index.
  2. Iterate over the array nums from left to right.
  3. For each element, check if it extends a consecutive subarray from the previous element by verifying if the difference is +1 or -1.
  4. If it does extend the consecutive subarray, update current_sum to include the sum contribution of the new subarray ending at this element. This is done by adding the value of the current element to current_sum.
  5. If it does not extend the consecutive subarray, reset current_sum to the value of the current element, as this starts a new segment of consecutive subarrays.
  6. Add current_sum to total_sum modulo $10^9 + 7$ at each step.
  7. Continue until the end of the array and return total_sum.

Why it works: Each element contributes to all consecutive subarrays that end at that element. By tracking the cumulative sum of subarrays ending at each index, we ensure that every subarray is counted exactly once, and modulo arithmetic prevents overflow.

Python Solution

from typing import List

class Solution:
    def getSum(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        total_sum = 0
        current_sum = 0
        
        for i, num in enumerate(nums):
            if i > 0 and abs(nums[i] - nums[i - 1]) == 1:
                current_sum = (current_sum + num) % MOD
            else:
                current_sum = num % MOD
            total_sum = (total_sum + current_sum) % MOD
        
        return total_sum

In this implementation, current_sum keeps track of the cumulative sum of consecutive subarrays ending at the current element. If the current element continues a consecutive pattern, we add its value to current_sum. Otherwise, we start a new sequence. We add current_sum to total_sum at each step, ensuring that all subarrays are counted efficiently.

Go Solution

func getSum(nums []int) int {
    const MOD = 1_000_000_007
    totalSum := 0
    currentSum := 0

    for i, num := range nums {
        if i > 0 && (nums[i]-nums[i-1] == 1 || nums[i]-nums[i-1] == -1) {
            currentSum = (currentSum + num) % MOD
        } else {
            currentSum = num % MOD
        }
        totalSum = (totalSum + currentSum) % MOD
    }
    
    return totalSum
}

The Go implementation mirrors the Python logic closely. We explicitly handle modulo arithmetic and slice indexing. Since Go does not have Python's large integer support, modulo ensures no overflow occurs.

Worked Examples

Example 1: nums = [1,2,3]

Index num current_sum total_sum Notes
0 1 1 1 Single element, start of new subarray
1 2 3 4 Continues consecutive +1, add 2 to previous current_sum 1 -> 3
2 3 6 10 Continues consecutive +1, add 3 to previous current_sum 3 -> 6

Total sum: 20

Example 2: nums = [1,3,5,7]

All elements are isolated, so each current_sum equals the element. Total sum = 1 + 3 + 5 + 7 = 16.

Example 3: nums = [7,6,1,2]

Index num current_sum total_sum Notes
0 7 7 7 Single element
1 6 13 20 Consecutive -1, add 6 to previous 7 -> 13
2 1 1 21 Not consecutive with previous, reset current_sum
3 2 3 24 Consecutive +1, add 2 to previous 1 -> 3

Total sum: 32

Complexity Analysis

Measure Complexity Explanation
Time O(n) Single pass through the array to accumulate consecutive subarray sums
Space O(1) Only constant variables used, no extra data structures

Since each element is visited exactly once, the algorithm is linear. The space complexity is constant because we only maintain sums, no additional storage is required.

Test Cases

# test cases
sol = Solution()

assert sol.getSum([1,2,3]) == 20  # basic consecutive increasing
assert sol.getSum([1,3,5,7]) == 16  # all isolated elements
assert sol.getSum([7,6,1,2]) == 32  # mix of increasing and decreasing
assert sol.getSum([1]) == 1  # single element
assert sol.getSum([1,2,1,2,1]) == 15  # alternating consecutive sequences
assert sol.getSum([100000]*5) == 500000  # all identical elements
assert sol.getSum([1,2,3,4,3,2,1]) == 50  # long consecutive increasing then decreasing
Test Why
[1,2,3] Validates basic consecutive increasing pattern
[1,3,5,7] Validates isolated elements handling
[7,6,1,2] Mix of decreasing and isolated subsequences
[1] Edge case of single element
[1,2,1,2,1] Alternating consecutive sequences
[100000]*5 Edge case with identical elements, not consecutive
[1,2,3,4,3,2,1] Longer sequences with increasing then decreasing

Edge Cases

The first edge case is a single-element array. This tests whether the implementation correctly counts length-1 subarrays as consecutive, which our solution handles by initializing current_sum with the element value.

The second edge case involves arrays with repeated identical elements. Since consecutive requires a difference of ±1, identical elements do not extend a consecutive subarray, so current_sum is reset at each duplicate. This prevents overcounting.

The third edge case is arrays with alternating increases and decreases, such as [1,2,1,2]. Here, new consecutive sequences start frequently. The solution correctly resets current_sum whenever the consecutive condition fails, ensuring that each subarray is counted exactly once without overlap or omission.