Sum of Subsequence Widths - Practice Coding Problems

Sum of Subsequence Widths - Problem

The width of a sequence is the difference between the maximum and minimum elements in the sequence.

Given an array of integers nums, return the sum of the widths of all the non-empty subsequences of nums. Since the answer may be very large, return it modulo 10^9 + 7.

A subsequence is a sequence that can be derived from an array by deleting some or no elements without changing the order of the remaining elements. For example, [3,6,2,7] is a subsequence of the array [0,3,1,6,2,2,7].

Input & Output

Example 1 — Basic Case

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

› Output: 6

💡 Note: All subsequences: [2]→0, [1]→0, [3]→0, [2,1]→1, [2,3]→1, [1,3]→2, [2,1,3]→2. Sum = 0+0+0+1+1+2+2 = 6

Example 2 — Single Element

$ Input: nums = [5]

› Output: 0

💡 Note: Only one subsequence [5] with width = 5-5 = 0

Example 3 — Two Elements

$ Input: nums = [1,4]

› Output: 6

💡 Note: Subsequences: [1]→0, [4]→0, [1,4]→3. Sum = 0+0+3 = 3. Wait, let me recalculate: [1,4]→4-1=3. Total = 3

Constraints

1 ≤ nums.length ≤ 20000
-10⁴ ≤ nums[i] ≤ 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Array [2, 1, 3] with all possible subsequences

Calculate Widths

Find max-min for each subsequence

Sum Results

Add all widths: 0+0+0+1+1+2+2 = 6

Key Takeaway

🎯 Key Insight: After sorting, each element's contribution can be calculated mathematically using powers of 2

Asked in

G Google 45 a Amazon 35 M Microsoft 30

The key insight is to sort the array first, then use mathematical formulas to calculate how many times each element appears as maximum or minimum across all subsequences. Best approach uses sorting + combinatorics. Time: O(n log n), Space: O(1)

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force - Generate All Subsequences	O(n × 2^n)	O(n)	Generate all possible subsequences and calculate width for each
Sort and Mathematical Formula	O(n log n)	O(1)	Sort array first, then use mathematical insight about contribution of each element

Brute Force - Generate All Subsequences — Algorithm Steps

Step 1: Generate all 2^n - 1 non-empty subsequences
Step 2: For each subsequence, find max and min elements
Step 3: Calculate width (max - min) and add to total sum

Visualization

Tap to expand

Step-by-Step Walkthrough

Input Array

Start with array [2, 1, 3]

Generate Subsequences

Create all 7 non-empty subsequences using bit masks

Calculate Widths

For each subsequence, find max - min and sum them up

Code -

solution.c — C

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

int solution(int* nums, int n) {
    const int MOD = 1000000007;
    long long total = 0;
    
    // Generate all non-empty subsequences using bit manipulation
    for (int mask = 1; mask < (1 << n); mask++) {
        int subsequence[20];
        int subLen = 0;
        
        for (int i = 0; i < n; i++) {
            if (mask & (1 << i)) {
                subsequence[subLen++] = nums[i];
            }
        }
        
        // Calculate width of this subsequence
        if (subLen > 0) {
            int maxVal = subsequence[0], minVal = subsequence[0];
            for (int i = 1; i < subLen; i++) {
                if (subsequence[i] > maxVal) maxVal = subsequence[i];
                if (subsequence[i] < minVal) minVal = subsequence[i];
            }
            long long width = maxVal - minVal;
            total = (total + width) % MOD;
        }
    }
    
    return total;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse array manually
    int nums[20];
    int n = 0;
    char* token = strtok(line + 1, ",]");
    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^n)

2^n subsequences, each requiring O(n) time to find max and min

⚠ Quadratic Growth

Space Complexity

O(n)

Space to store current subsequence and recursion stack

⚡ Linearithmic Space

28.0K Views

Medium Frequency

~35 min Avg. Time

850 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 - Generate All Subsequences — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler