LeetCode 891: Sum of Subsequence Widths

Problem Restatement

We are given an integer array nums.

For any non-empty subsequence, its width is:

maximum value - minimum value

Return the sum of widths of all non-empty subsequences.

Because the answer can be very large, return it modulo:

10**9 + 7

A subsequence is formed by deleting zero or more elements without changing the order of the remaining elements. The problem asks for the sum of widths across all non-empty subsequences.

Input and Output

Function shape:

def sumSubseqWidths(self, nums: list[int]) -> int:
    ...

Examples

Example 1:

Input: nums = [2,1,3]
Output: 6

The non-empty subsequences are:

Total:

0 + 0 + 0 + 1 + 1 + 2 + 2 = 6

Example 2:

Input: nums = [2]
Output: 0

There is only one non-empty subsequence:

[2]

Its maximum and minimum are both 2, so its width is 0.

First Thought: Generate Every Subsequence

A direct approach is to generate every non-empty subsequence.

For each subsequence:

1. Find its minimum.
2. Find its maximum.
3. Add maximum - minimum to the answer.

This is correct for small arrays.

But an array of length n has:

2^n - 1

non-empty subsequences.

So this approach is too slow.

Key Insight

We do not need to inspect each subsequence directly.

Instead, count how much each number contributes as a maximum and as a minimum.

Sort the array first:

nums.sort()

After sorting, suppose nums[i] is chosen as the maximum of a subsequence.

Then every other chosen element must come from the i elements before it:

nums[0], nums[1], ..., nums[i - 1]

Each of those earlier elements may be included or excluded.

So nums[i] is the maximum in:

2^i

subsequences.

Similarly, if nums[i] is chosen as the minimum, then every other chosen element must come from the n - i - 1 elements after it.

So nums[i] is the minimum in:

2^(n - i - 1)

subsequences.

Therefore, the net contribution of nums[i] is:

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

Add this for every index.

Algorithm

Sort nums.

Precompute powers of two modulo MOD:

pow2[i] = 2^i % MOD

Then for each index i:

1. Add its contribution as maximum:

nums[i] * pow2[i]

2. Subtract its contribution as minimum:

nums[i] * pow2[n - i - 1]

Return the answer modulo MOD.

Walkthrough

Use:

nums = [2, 1, 3]

After sorting:

[1, 2, 3]

Powers of two:

Contribution by index:

Total:

-3 + 0 + 9 = 6

So the answer is 6.

Correctness

After sorting, every subsequence has a smallest selected index and a largest selected index.

For an element nums[i] to be the maximum of a subsequence, the subsequence must include nums[i], and every other selected element must come from indices before i. There are i such earlier elements, and each can be either selected or skipped. Therefore, nums[i] appears as the maximum in exactly 2^i subsequences.

For nums[i] to be the minimum of a subsequence, the subsequence must include nums[i], and every other selected element must come from indices after i. There are n - i - 1 such later elements, so nums[i] appears as the minimum in exactly 2^(n - i - 1) subsequences.

The width of each subsequence is its maximum minus its minimum. By summing all maximum contributions and subtracting all minimum contributions, every subsequence contributes exactly its width once.

Therefore, the algorithm computes the sum of widths of all non-empty subsequences.

Complexity

Let:

n = len(nums)

Implementation

class Solution:
    def sumSubseqWidths(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)

        nums.sort()

        pow2 = [1] * n
        for i in range(1, n):
            pow2[i] = (pow2[i - 1] * 2) % MOD

        answer = 0

        for i, value in enumerate(nums):
            as_max = value * pow2[i]
            as_min = value * pow2[n - i - 1]
            answer += as_max - as_min
            answer %= MOD

        return answer

Code Explanation

We sort the array:

nums.sort()

Sorting lets us reason about which values can be smaller or larger than each element.

Then we precompute powers of two:

pow2 = [1] * n
for i in range(1, n):
    pow2[i] = (pow2[i - 1] * 2) % MOD

For each element:

for i, value in enumerate(nums):

it contributes positively when it is a maximum:

as_max = value * pow2[i]

and negatively when it is a minimum:

as_min = value * pow2[n - i - 1]

We add the net contribution:

answer += as_max - as_min
answer %= MOD

The modulo keeps the answer bounded.

Space-Optimized Implementation

We can avoid the pow2 array by pairing symmetric indices.

For sorted nums, the answer can also be written as:

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

Code:

class Solution:
    def sumSubseqWidths(self, nums: list[int]) -> int:
        MOD = 10**9 + 7
        n = len(nums)

        nums.sort()

        answer = 0
        power = 1

        for i in range(n):
            answer += (nums[i] - nums[n - 1 - i]) * power
            answer %= MOD
            power = (power * 2) % MOD

        return answer

This version uses O(1) extra space.

Testing

def run_tests():
    s = Solution()

    assert s.sumSubseqWidths([2, 1, 3]) == 6
    assert s.sumSubseqWidths([2]) == 0
    assert s.sumSubseqWidths([1, 2]) == 1
    assert s.sumSubseqWidths([1, 1, 1]) == 0
    assert s.sumSubseqWidths([1, 2, 3, 4]) == 23

    print("all tests passed")

run_tests()

Test meaning: