LeetCode 891 - Sum of Subsequence Widths

The problem asks us to calculate the sum of widths for all non-empty subsequences of a given integer array nums. A subsequence is any sequence derived by removing zero or more elements from the original array while maintaining the order.

leetcodehardarraymathsorting

LeetCode Problem 891

Difficulty: 🔴 Hard
Topics: Array, Math, Sorting

Solution

Problem Understanding

The problem asks us to calculate the sum of widths for all non-empty subsequences of a given integer array nums. A subsequence is any sequence derived by removing zero or more elements from the original array while maintaining the order. The width of a sequence is defined as the difference between its maximum and minimum elements.

The input nums is an array of integers with constraints 1 <= nums.length <= 10^5 and 1 <= nums[i] <= 10^5. The output is the sum of the widths of all non-empty subsequences modulo 10^9 + 7. Since the number of subsequences grows exponentially (2^n), a naive approach that explicitly generates every subsequence would be infeasible for large inputs.

Key edge cases include arrays of length 1 (where all subsequences have width 0), arrays with duplicate elements, and already sorted arrays. The problem guarantees non-empty input and positive integers, which simplifies handling of negative or empty cases.

Approaches

Brute Force Approach

The brute-force solution would generate all possible non-empty subsequences of nums, compute the maximum and minimum for each, then sum up the differences. This approach is correct logically but impractical because generating all subsequences has a time complexity of O(2^n), which is far too slow for n up to 10^5.

Optimal Approach

The key observation for an optimal solution is that each element contributes to multiple subsequences as either the maximum or the minimum. If we sort the array, we can compute how many subsequences an element contributes to as the maximum and how many as the minimum. Specifically, for a sorted array:

  • nums[i] is the maximum in 2^i subsequences formed by choosing any combination of elements before it.
  • nums[i] is the minimum in 2^(n-1-i) subsequences formed by choosing any combination of elements after it.

Thus, the total contribution of nums[i] to the sum of widths is:

nums[i] * (2^i - 2^(n-1-i))

We sum these contributions for all elements and take modulo 10^9 + 7.

Approach Time Complexity Space Complexity Notes
Brute Force O(2^n * n) O(2^n * n) Generates all subsequences explicitly, impractical for n ~ 10^5
Optimal O(n log n) O(n) Uses sorting and precomputed powers of 2, efficient for large arrays

Algorithm Walkthrough

  1. Sort the array nums in ascending order. Sorting ensures that elements at lower indices are smaller than those at higher indices.
  2. Precompute powers of 2 modulo 10^9 + 7 for indices from 0 to n-1. This allows fast computation of contributions for each element.
  3. Initialize a variable total to accumulate the sum of widths.
  4. Iterate through the array by index i:
  • Compute the number of subsequences where nums[i] is the maximum: 2^i.
  • Compute the number of subsequences where nums[i] is the minimum: 2^(n-1-i).
  • Update total by adding the difference multiplied by nums[i] modulo 10^9 + 7.
  1. Return total modulo 10^9 + 7.

Why it works: Each element's contribution to the width of a subsequence can be broken down into its role as a maximum or minimum. Sorting ensures we know these contributions exactly without generating subsequences. Summing across all elements accounts for all subsequences.

Python Solution

from typing import List

class Solution:
    def sumSubseqWidths(self, nums: List[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)
        nums.sort()
        
        # Precompute powers of 2 modulo MOD
        pow2 = [1] * n
        for i in range(1, n):
            pow2[i] = (pow2[i-1] * 2) % MOD
        
        total = 0
        for i in range(n):
            total = (total + nums[i] * (pow2[i] - pow2[n-1-i])) % MOD
        
        return total

Explanation: We first sort the array to establish order. The pow2 array stores powers of 2 modulo 10^9 + 7 for quick computation. For each element, we calculate its net contribution as maximum - minimum across all subsequences it participates in. The modulo ensures no integer overflow.

Go Solution

func sumSubseqWidths(nums []int) int {
    const MOD = 1_000_000_007
    n := len(nums)
    
    // Sort the array
    sort.Ints(nums)
    
    // Precompute powers of 2 modulo MOD
    pow2 := make([]int, n)
    pow2[0] = 1
    for i := 1; i < n; i++ {
        pow2[i] = (pow2[i-1] * 2) % MOD
    }
    
    total := 0
    for i := 0; i < n; i++ {
        contribution := ((pow2[i] - pow2[n-1-i]) * nums[i]) % MOD
        total = (total + contribution + MOD) % MOD // handle negative
    }
    
    return total
}

Go-specific notes: Go requires handling negative modulo results, hence the + MOD before final modulo. sort.Ints is used for sorting, and slices are used for dynamic arrays. Overflow is avoided using modulo at every step.

Worked Examples

Example 1: nums = [2,1,3]

After sorting: [1,2,3]

Precompute powers: [1,2,4]

i nums[i] pow2[i] pow2[n-1-i] Contribution Total
0 1 1 4 1*(1-4)=-3 0+(-3)= -3 → 1000000004
1 2 2 2 2*(2-2)=0 1000000004+0=1000000004
2 3 4 1 3*(4-1)=9 1000000004+9=1000000013 → 6 (mod 10^9+7)

Output: 6

Example 2: nums = [2]

Sorted: [2], pow2: [1]

Contribution: 2*(1-1)=0

Output: 0

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Sorting dominates, precomputing powers and iterating are O(n)
Space O(n) Store powers of 2 and intermediate sum

The algorithm is efficient because it avoids generating subsequences explicitly, instead leveraging combinatorial counting and modulo arithmetic.

Test Cases

# Basic examples
assert Solution().sumSubseqWidths([2,1,3]) == 6  # Example 1
assert Solution().sumSubseqWidths([2]) == 0     # Example 2

# Edge cases
assert Solution().sumSubseqWidths([1,1,1]) == 0 # All elements equal
assert Solution().sumSubseqWidths([1,2,3,4]) == 20 # Small array

# Large numbers
assert Solution().sumSubseqWidths([10**5]*5) == 0 # Max elements, equal

# Mixed elements
assert Solution().sumSubseqWidths([3,6,2,7]) == 61

# Single element repeated
assert Solution().sumSubseqWidths([5]*10) == 0
Test Why
[2,1,3] Validates basic example with multiple widths
[2] Tests single element edge case
[1,1,1] Ensures duplicates contribute zero width
[1,2,3,4] Tests sorted array behavior
[10**5]*5 Tests handling of large numbers, all equal
[3,6,2,7] General case with unordered numbers
[5]*10 Repeated element scenario

Edge Cases

The first edge case is an array with a single element. Since there is only one subsequence [x], its width is 0. Our algorithm correctly handles this because pow2[0] - pow2[0] = 0.

The second edge case is an array where all elements are equal. Any subsequence will have width 0, and our formula naturally computes nums[i] * (2^i - 2^(n-1-i)) = 0 for each element.

The third edge case is large arrays near the upper constraint (length 10^5). Generating subsequences explicitly is impossible, but precomputing powers and using the sorted array approach ensures the algorithm runs efficiently without memory issues. The modulo