Facebook Pixel

3284. Sum of Consecutive Subarrays 🔒

MediumArrayTwo PointersDynamic Programming
Leetcode Link

Problem Description

We define an array arr of length n as consecutive if it satisfies one of the following conditions:

  • For all 1 <= i < n, arr[i] - arr[i - 1] == 1.
  • For all 1 <= i < n, arr[i] - arr[i - 1] == -1.

The value of an array is the sum of its elements.

For example, [3, 4, 5] is a consecutive array with a value of 12, and [9, 8] is another with a value of 17. Arrays like [3, 4, 3] and [8, 6] are not consecutive.

Given an array of integers nums, the task is to return the sum of the values of all consecutive subarrays in nums.

Since the result may be large, return it modulo 10^9 + 7.

Note: An array of length 1 is considered consecutive.

Quick Interview Experience
Help others by sharing your interview experience
Have you seen this problem before?

Intuition

The goal here is to find all consecutive subarrays in nums and calculate the sum of their values. A key observation is that a consecutive subarray can be either strictly increasing or strictly decreasing by 1.

We keep track of two key metrics for each element in the array:

  • f, the length of the current increasing subarray ending at the current element.
  • g, the length of the current decreasing subarray ending at the current element.

Simultaneously, we maintain:

  • s, the cumulative sum of the increasing subarray values.
  • t, the cumulative sum of the decreasing subarray values.

Initially, start with f = g = 1 and s = t = nums[0] because a single-element array is considered consecutive. We traverse the array starting from the second element:

  1. If the current element extends the increasing sequence (nums[i] - nums[i-1] == 1), increment f and update s. Add s to the cumulative answer.

  2. If the current element extends the decreasing sequence (nums[i] - nums[i-1] == -1), increment g and update t. Add t to the cumulative answer.

  3. If neither condition holds, treat the current element as the start of a new consecutive subarray and add its value to the cumulative answer.

By tracking the sum of all cumulative subarray values using these metrics, we can efficiently compute the desired result, ensuring that it remains manageable by applying a modulo 10^9 + 7.

Learn more about Two Pointers and Dynamic Programming patterns.

Solution Approach

To tackle this problem efficiently, we utilize a combination of dynamic programming concepts and a single pass approach over the array nums. Here's a detailed walkthrough of the implementation:

  1. Initialize Variables:

    • mod = 10**9 + 7 to keep the results manageable with large numbers.
    • f and g to track the lengths of current consecutive increasing and decreasing subarrays, respectively. Set both to 1 initially as each element alone is a valid subarray.
    • s and t to hold the sums of these increasing and decreasing subarrays. Initialize them with the first element of nums, i.e., s = t = nums[0].
    • ans to accumulate the total value of all consecutive subarrays, starting with the value of the first element, ans = nums[0].

  2. Iterate through the Array:

    • We use the pairwise function from the itertools module to iterate over consecutive pairs in nums.
    • For each pair (x, y):
      • Increasing Subarray: If y extends the increasing sequence (y - x == 1), increase f by 1 and update s with s += f * y. Then, add s to ans with modulo, ans = (ans + s) % mod.
      • Decreasing Subarray: If y belongs to a decreasing sequence (y - x == -1), increase g by 1 and update t with t += g * y. Then, add t to ans with modulo, ans = (ans + t) % mod.
      • Reset: If neither condition is met, reset both f and g to 1, and start separate subarrays with s = t = y. Also, add y directly to ans under the current context.

  3. Return the Result:

    • After completing the iteration, ans holds the required sum of the values of all consecutive subarrays. Return ans as the function's result.

This approach efficiently computes the desired sum by leveraging linear traversal and maintaining updated sums and lengths dynamically, thereby avoiding redundant calculations.

Ready to land your dream job?

Unlock your dream job with a 3-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

Let's consider an example array nums = [2, 3, 2, 1, 2].

  1. Initialization:

    • mod = 10**9 + 7
    • f = 1, g = 1
    • s = 2, t = 2 (Because the first element is 2)
    • ans = 2

  2. First Iteration (pair: 2, 3):

    • 3 - 2 = 1, indicating an increasing subarray.
    • Increase f by 1: f = 2
    • Update s: s += 2 * 3 = 8
    • Add s to ans: ans = (2 + 8) % mod = 10

  3. Second Iteration (pair: 3, 2):

    • 2 - 3 = -1, indicating a decreasing subarray.
    • Increase g by 1: g = 2
    • Update t: t += 2 * 2 = 6
    • Add t to ans: ans = (10 + 6) % mod = 16

  4. Third Iteration (pair: 2, 1):

    • 1 - 2 = -1, indicating a continuing decreasing subarray.
    • Increase g by 1: g = 3
    • Update t: t += 3 * 1 = 9
    • Add t to ans: ans = (16 + 9) % mod = 25

  5. Fourth Iteration (pair: 1, 2):

    • 2 - 1 = 1, indicating a new increasing subarray starting.
    • Reset f = 1, since it's a new start.
    • Set s = 2
    • g = 1 (reset, new sequence starts)
    • Set t = 2
    • Add 2 directly to ans: ans = (25 + 2) % mod = 27

After iterating through the entire array, the sum of the values of all consecutive subarrays is 27. Thus, the function returns 27 as the final result.

Solution Implementation

1from itertools import pairwise
2from typing import List
3
4class Solution:
5    def getSum(self, nums: List[int]) -> int:
6        # Define the modulus value as 10^9 + 7
7        modulus = 10**9 + 7
8
9        # Initialize sequence counters and sums
10        increasing_count = decreasing_count = 1
11        increasing_sum = decreasing_sum = nums[0]
12
13        # Initialize the answer with the first element
14        answer = nums[0]
15
16        # Iterate through pairs of consecutive elements in the list
17        for current, next_element in pairwise(nums):
18            # Check if the sequence is strictly increasing
19            if next_element - current == 1:
20                increasing_count += 1
21                increasing_sum += increasing_count * next_element
22                answer = (answer + increasing_sum) % modulus
23            else:
24                increasing_count = 1
25                increasing_sum = next_element
26
27            # Check if the sequence is strictly decreasing
28            if next_element - current == -1:
29                decreasing_count += 1
30                decreasing_sum += decreasing_count * next_element
31                answer = (answer + decreasing_sum) % modulus
32            else:
33                decreasing_count = 1
34                decreasing_sum = next_element
35
36            # If there is no consecutive increasing or decreasing step
37            if abs(next_element - current) != 1:
38                answer = (answer + next_element) % modulus
39
40        return answer
41
1class Solution {
2    public int getSum(int[] nums) {
3        final int MOD = (int) 1e9 + 7; // Define the modulus for large integer handling.
4        long sumConsecutiveIncreasing = nums[0]; // Sum for consecutive increasing sequence.
5        long sumConsecutiveDecreasing = nums[0]; // Sum for consecutive decreasing sequence.
6        long result = nums[0]; // Result initialized with the first element.
7        int incrCount = 1; // Counter for increasing sequences.
8        int decrCount = 1; // Counter for decreasing sequences.
9
10        for (int i = 1; i < nums.length; ++i) {
11            int prev = nums[i - 1]; // Previous element in the array.
12            int curr = nums[i]; // Current element in the array.
13
14            // If the sequence is increasing consecutively.
15            if (curr - prev == 1) {
16                ++incrCount; // Increment the counter for increasing sequences.
17                sumConsecutiveIncreasing += 1L * incrCount * curr; // Update the sum with the current element.
18                result = (result + sumConsecutiveIncreasing) % MOD; // Update result ensuring it's within MOD.
19            } else {
20                incrCount = 1; // Reset the increasing counter.
21                sumConsecutiveIncreasing = curr; // Set sum to the current element.
22            }
23          
24            // If the sequence is decreasing consecutively.
25            if (curr - prev == -1) {
26                ++decrCount; // Increment the counter for decreasing sequences.
27                sumConsecutiveDecreasing += 1L * decrCount * curr; // Update the sum with the current element.
28                result = (result + sumConsecutiveDecreasing) % MOD; // Update result ensuring it's within MOD.
29            } else {
30                decrCount = 1; // Reset the decreasing counter.
31                sumConsecutiveDecreasing = curr; // Set sum to the current element.
32            }
33
34            // If the current and previous elements are not consecutive in either direction.
35            if (Math.abs(curr - prev) != 1) {
36                result = (result + curr) % MOD; // Add the current element to the result enforcing the MOD.
37            }
38        }
39
40        return (int) result; // Convert result back to an integer and return.
41    }
42}
43
1class Solution {
2public:
3    int getSum(vector<int>& nums) {
4        const int mod = 1e9 + 7;  // Modulo value for preventing overflow
5        long long increasingSum = nums[0];
6        long long decreasingSum = nums[0];
7        long long totalSum = nums[0];
8        int increasingCount = 1;
9        int decreasingCount = 1;
10
11        for (int i = 1; i < nums.size(); ++i) {
12            int previousNum = nums[i - 1];
13            int currentNum = nums[i];
14
15            // Handle increasing sequences
16            if (currentNum - previousNum == 1) {
17                // If current number continues increasing sequence
18                ++increasingCount;
19                increasingSum += 1LL * increasingCount * currentNum;
20                totalSum = (totalSum + increasingSum) % mod;
21            } else {
22                // Reset for new increasing sequence
23                increasingCount = 1;
24                increasingSum = currentNum;
25            }
26
27            // Handle decreasing sequences
28            if (currentNum - previousNum == -1) {
29                // If current number continues decreasing sequence
30                ++decreasingCount;
31                decreasingSum += 1LL * decreasingCount * currentNum;
32                totalSum = (totalSum + decreasingSum) % mod;
33            } else {
34                // Reset for new decreasing sequence
35                decreasingCount = 1;
36                decreasingSum = currentNum;
37            }
38
39            // Account for numbers not part of increasing or decreasing sequence
40            if (abs(currentNum - previousNum) != 1) {
41                totalSum = (totalSum + currentNum) % mod;
42            }
43        }
44        return totalSum;
45    }
46};
47
1// Function to calculate a modified cumulative sum based on consecutive sequences in an array
2function getSum(nums: number[]): number {
3    const mod = 10 ** 9 + 7; // Constant value for modulo operation to prevent overflow
4    let increasingCount = 1, decreasingCount = 1; // Track lengths of increasing and decreasing sequences
5    let increasingSum = nums[0], decreasingSum = nums[0]; // Sum of increasing and decreasing sequences
6    let result = nums[0]; // Resultant sum initialized with the first element
7
8    // Iterate through the array starting from the second element
9    for (let i = 1; i < nums.length; i++) {
10        const previous = nums[i - 1];
11        const current = nums[i];
12
13        // Check if current element continues an increasing sequence
14        if (current - previous === 1) {
15            increasingCount++;
16            increasingSum += increasingCount * current;
17            result = (result + increasingSum) % mod;
18        } else {
19            increasingCount = 1;
20            increasingSum = current;
21        }
22
23        // Check if current element continues a decreasing sequence
24        if (current - previous === -1) {
25            decreasingCount++;
26            decreasingSum += decreasingCount * current;
27            result = (result + decreasingSum) % mod;
28        } else {
29            decreasingCount = 1;
30            decreasingSum = current;
31        }
32
33        // Add current element to result if it doesn't belong to an increasing or decreasing sequence
34        if (Math.abs(current - previous) !== 1) {
35            result = (result + current) % mod;
36        }
37    }
38
39    return result; // Return the calculated result
40}
41

Time and Space Complexity

The time complexity of the code is O(n), where n is the length of the input list nums. This is because the code iterates through the list using pairwise, which processes each element exactly once. The operations inside the loop, such as conditional checks and arithmetic operations, all take constant time.

The space complexity of the code is O(1). The algorithm only uses a fixed amount of extra space for variables like mod, f, g, s, t, and ans, regardless of the size of the input list nums.

Learn more about how to find time and space complexity quickly.

Discover Your Strengths and Weaknesses: Take Our 3-Minute Quiz to Tailor Your Study Plan:

Which data structure is used to implement recursion?

Recommended Readings

Tech Interview Pattern | Two Pointers Introduction

Tech Interview Pattern Two Pointers Introduction If you prefer videos here's a super quick introduction to Two Pointers div class responsive iframe iframe src https www youtube com embed xZ4AfXHQ1VQ title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture allowfullscreen iframe div Two pointers is a common interview

Dynamic Programming Introduction and Patterns

What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution

Coding Interview Patterns: The Smart, Data-Driven Way to Prepare for Tech Interviews

Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way

Want a Structured Path to Master System Design Too? Don’t Miss This!

Load More