Sum of Consecutive Subsequences - Practice Coding Problems

Sum of Consecutive Subsequences - Problem

We call an array consecutive if one of the following holds:

arr[i] - arr[i - 1] == 1 for all 1 <= i < n (strictly increasing by 1)
arr[i] - arr[i - 1] == -1 for all 1 <= i < n (strictly decreasing by 1)

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 non-empty subsequences. Since the answer may be very large, return it modulo 10⁹ + 7.

Note that an array of length 1 is also considered consecutive.

Input & Output

Example 1 — Basic Consecutive Sequences

$ Input: nums = [1,2,4]

› Output: 10

💡 Note: Consecutive subsequences: [1] (sum=1), [2] (sum=2), [4] (sum=4), [1,2] (sum=3). Total = 1+2+4+3 = 10

Example 2 — Decreasing Sequence

$ Input: nums = [3,2]

› Output: 8

💡 Note: Consecutive subsequences: [3] (sum=3), [2] (sum=2), [3,2] (sum=5). Total = 3+2+5 = 8

Example 3 — Single Element

$ Input: nums = [5]

› Output: 5

💡 Note: Only one subsequence possible: [5] with sum = 5

Constraints

1 ≤ nums.length ≤ 10⁵
-10⁶ ≤ nums[i] ≤ 10⁶

Visualization

Tap to expand

Understanding the Visualization

Input

Array [1,2,4] - find all consecutive subsequences

Process

Identify consecutive patterns (differ by ±1)

Output

Sum values: 1+2+4+3 = 10

Key Takeaway

🎯 Key Insight: Use DP to efficiently track consecutive sequences ending at each position rather than checking all 2^n subsequences

Asked in

G Google 15 M Meta 12 A Amazon 8

The key insight is to use dynamic programming to track consecutive sequences ending at each position. We maintain states for both increasing and decreasing sequences, avoiding the exponential brute force approach. Best approach is DP with Hash Map: Time: O(n), Space: O(n)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Check All Subsequences	O(n × 2ⁿ)	O(n)	Generate all possible subsequences and check if each is consecutive
Dynamic Programming with Hash Map	O(n)	O(n)	Track consecutive subsequences ending at each position using DP

Brute Force - Check All Subsequences — Algorithm Steps

Generate all 2^n possible subsequences
For each subsequence, check if consecutive
If consecutive, add sum to result

Visualization

Tap to expand

Step-by-Step Walkthrough

Generate

Create all 2^n subsequences using bitmask

Validate

Check if each subsequence is consecutive

Sum

Add values of valid consecutive subsequences

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

int solution(int* nums, int n) {
    int MOD = 1000000007;
    long long total = 0;
    
    // Generate all 2^n subsequences
    for (int mask = 1; mask < (1 << n); mask++) {
        int subseq[20];
        int len = 0;
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subseq[len++] = nums[i];
            }
        }
        
        // Check if consecutive
        if (len == 1) {
            total = (total + subseq[0]) % MOD;
        } else {
            int consecutive = 1;
            int diff = subseq[1] - subseq[0];
            if (abs(diff) != 1) {
                consecutive = 0;
            } else {
                for (int j = 2; j < len; j++) {
                    if (subseq[j] - subseq[j-1] != diff) {
                        consecutive = 0;
                        break;
                    }
                }
            }
            
            if (consecutive) {
                long long sum = 0;
                for (int j = 0; j < len; j++) {
                    sum += subseq[j];
                }
                total = (total + sum) % MOD;
            }
        }
    }
    
    return total;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[20];
    int n = 0;
    char* ptr = strchr(line, '[') + 1;
    char* token = strtok(ptr, ",]");
    while (token != NULL) {
        nums[n++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, n);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × 2ⁿ)

2^n subsequences, each taking O(n) time to validate and sum

✓ Linear Growth

Space Complexity

O(n)

Space for storing current subsequence during generation

⚡ Linearithmic Space

23.0K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force - Check All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler