We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Sum of Consecutive Subarrays

Number: 3602

Difficulty: Medium

Paid? Yes

Companies: N/A

Problem Description

Given an array of integers nums, a subarray is called consecutive if the differences between adjacent elements are either 1 (increasing) or -1 (decreasing). Even a single element is considered consecutive. The value of a subarray is defined as the sum of its elements. The task is to compute the sum of the values of all consecutive subarrays within nums. Since the result can be very large, return it modulo 10^9+7.

Key Insights

  • Every individual element constitutes a valid consecutive subarray.
  • A dynamic programming (DP) or one-pass approach can be used to aggregate contributions from subarrays ending at each index.
  • If nums[i] continues a consecutive pattern (difference of exactly 1 or -1 from nums[i-1]), then all consecutive subarrays ending at i−1 can be extended to i.
  • Use a count to represent how many consecutive subarrays end at the previous element and update the cumulative sum accordingly.
  • The recurrence: If consecutive, then:   count[i] = count[i-1] + 1
      dp[i] = nums[i] + dp[i-1] + (count[i-1]) * nums[i]
    Otherwise, reset count[i] = 1 and dp[i] = nums[i].
  • The overall answer is the sum of dp[i] for all indices i.

Space and Time Complexity

Time Complexity: O(n) – we iterate through the list once.
Space Complexity: O(1) – only a few auxiliary variables are used.

Solution

We traverse the array while maintaining two variables: one for the cumulative sum of consecutive subarray sums ending at the previous index (prevSum) and another to keep the count of such subarrays (count). At each index, if the current element continues the consecutive pattern with the previous element (either increasing by 1 or decreasing by 1), we increment count and update prevSum by adding:   nums[i] (starting a new subarray), plus
  prevSum (extending all previous consecutive subarrays) plus
  (nums[i] multiplied by the previous count) (additional contribution when extending each subarray). If the pattern breaks, reset count to 1 and prevSum to nums[i]. The final answer is the modulo sum of all prevSum values computed over the traversal.

Code Solutions

MOD = 10**9 + 7

def sumConsecutiveSubarrays(nums):
    # Initialize total sum, previous subarray sum, and count of consecutive subarrays ending at previous index
    total = 0
    prev_sum = 0  
    count = 0      
    for i in range(len(nums)):
        # Check if current element continues consecutive pattern with previous element
        if i > 0 and (nums[i] - nums[i - 1] == 1 or nums[i] - nums[i - 1] == -1):
            count += 1
            # Update prev_sum: new subarray starting at i plus extension of all subarrays ending at i-1
            prev_sum = (nums[i] + prev_sum + (count - 1) * nums[i]) % MOD
        else:
            count = 1  # Reset count as consecutive property breaks; single element subarray is valid
            prev_sum = nums[i] % MOD
        # Add current subarray sums ending at i to the total
        total = (total + prev_sum) % MOD
    return total

# Example usage:
if __name__ == "__main__":
    print(sumConsecutiveSubarrays([1,2,3]))  # Expected output: 20
    print(sumConsecutiveSubarrays([1,3,5,7])) # Expected output: 16
    print(sumConsecutiveSubarrays([7,6,1,2])) # Expected output: 32
← Back to All Questions