#891

Hard

LeetCode Problem Workspace

Sum of Subsequence Widths

Calculate the sum of widths for all subsequences in an integer array using sorting and combinatorial math efficiently.

Problem Statement

Given an integer array nums, define the width of a sequence as the difference between its maximum and minimum values. Your task is to find the sum of widths for every non-empty subsequence of nums. Return the result modulo 10^9 + 7 because the sum can grow very large.

A subsequence is any sequence derived by deleting zero or more elements from nums without changing the order of remaining elements. For instance, [3,6,2,7] is a valid subsequence of [0,3,1,6,2,2,7]. You must compute contributions from all subsequences, emphasizing the effect of each element as potential maximum and minimum in array-based combinatorial calculations.

Examples

Example 1

Input: nums = [2,1,3]

Output: 6

The subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3]. The corresponding widths are 0, 0, 0, 1, 1, 2, 2. The sum of these widths is 6.

Example 2

Input: nums = [2]

Output: 0

Example details omitted.

Constraints

1 <= nums.length <= 105
1 <= nums[i] <= 105

Solution Approach

Sort the array

Sorting nums allows us to systematically consider each number's role as a maximum or minimum in subsequences. Once sorted, smaller numbers contribute primarily as minima, larger numbers as maxima, simplifying combinatorial calculations.

Use combinatorial counts

For each element at index i, compute its number of contributions as max using 2^i and as min using 2^(n-i-1). This leverages the pattern of subset formation and avoids enumerating all subsequences explicitly.

Sum modulo 10^9 + 7

Accumulate the contributions as sum += element * (2^i - 2^(n-i-1)) and take modulo 10^9 + 7 to handle large numbers efficiently without overflow, producing the final sum of widths for all subsequences.

Complexity Analysis

Metric	Value
Time	O(N \log N)
Space	O(N)

Sorting takes O(N log N) and computing contributions with precomputed powers of two requires O(N) space. Overall time complexity is O(N log N) dominated by sorting, and space is O(N) for storing powers and intermediate sums.

What Interviewers Usually Probe

Check if the candidate recognizes the impact of sorting to simplify max/min handling.
Look for combinatorial reasoning using powers of two rather than brute-force subsequence enumeration.
Notice if modulo arithmetic is applied correctly to avoid overflow issues.

Common Pitfalls or Variants

Common pitfalls

Attempting to generate all subsequences leads to exponential time complexity.
Ignoring modulo 10^9 + 7 can cause integer overflow for large arrays.
Miscounting contributions as max or min without considering array order after sorting.

Follow-up variants

Compute sum of widths for subsequences restricted to size k instead of all sizes.
Handle arrays with negative integers and compute subsequence width sums modulo a different prime.
Find subsequences where the width falls within a specific range and sum only those widths.

FAQ

What is the main pattern used in Sum of Subsequence Widths?

The pattern combines array sorting with combinatorial math to calculate each element's contribution as maximum and minimum efficiently.

Why do we sort the array before calculating subsequence widths?

Sorting ensures we can systematically identify which elements act as maxima and minima in subsequences, enabling combinatorial counting without full enumeration.

How is modulo 10^9 + 7 applied in this problem?

All cumulative sums are taken modulo 10^9 + 7 to prevent integer overflow from the potentially large total of subsequence widths.

Can we compute subsequence widths without combinatorial math?

Brute-force enumeration is possible but impractical; combinatorial math allows O(N log N) performance by counting contributions without generating all subsequences.

What is the time complexity for solving Sum of Subsequence Widths?

Sorting takes O(N log N), and contribution calculations take O(N), so overall time complexity is O(N log N) with O(N) extra space for powers of two.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

class Solution:
    def sumSubseqWidths(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        nums.sort()
        ans, p = 0, 1
        for i, v in enumerate(nums):
            ans = (ans + (v - nums[-i - 1]) * p) % mod
            p = (p << 1) % mod
        return ans

Continue Practicing

#910 smallest range ii #939 minimum area rectangle #973 k closest points to origin