3284. Sum of Consecutive Subarrays 🔒
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.
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:
-
If the current element extends the increasing sequence (
nums[i] - nums[i-1] == 1
), incrementf
and updates
. Adds
to the cumulative answer. -
If the current element extends the decreasing sequence (
nums[i] - nums[i-1] == -1
), incrementg
and updatet
. Addt
to the cumulative answer. -
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:
-
Initialize Variables:
mod = 10**9 + 7
to keep the results manageable with large numbers.f
andg
to track the lengths of current consecutive increasing and decreasing subarrays, respectively. Set both to1
initially as each element alone is a valid subarray.s
andt
to hold the sums of these increasing and decreasing subarrays. Initialize them with the first element ofnums
, 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]
.
-
Iterate through the Array:
- We use the
pairwise
function from theitertools
module to iterate over consecutive pairs innums
. - For each pair
(x, y)
:- Increasing Subarray: If
y
extends the increasing sequence (y - x == 1
), increasef
by 1 and updates
withs += f * y
. Then, adds
toans
with modulo,ans = (ans + s) % mod
. - Decreasing Subarray: If
y
belongs to a decreasing sequence (y - x == -1
), increaseg
by 1 and updatet
witht += g * y
. Then, addt
toans
with modulo,ans = (ans + t) % mod
. - Reset: If neither condition is met, reset both
f
andg
to1
, and start separate subarrays withs = t = y
. Also, addy
directly toans
under the current context.
- Increasing Subarray: If
- We use the
-
Return the Result:
- After completing the iteration,
ans
holds the required sum of the values of all consecutive subarrays. Returnans
as the function's result.
- After completing the iteration,
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 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's consider an example array nums = [2, 3, 2, 1, 2]
.
-
Initialization:
mod = 10**9 + 7
f = 1
,g = 1
s = 2
,t = 2
(Because the first element is 2)ans = 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
toans
:ans = (2 + 8) % mod = 10
-
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
toans
:ans = (10 + 6) % mod = 16
-
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
toans
:ans = (16 + 9) % mod = 25
-
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 toans
: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.
Which algorithm is best for finding the shortest distance between two points in an unweighted graph?
Recommended Readings
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
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 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!