# LeetCode 891: Sum of Subsequence Widths

## Problem Restatement

We are given an integer array `nums`.

For any non-empty subsequence, its width is:

```text
maximum value - minimum value
```

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

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

```python
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

| Item | Meaning |
|---|---|
| Input | `nums`, an integer array |
| Output | Sum of widths of all non-empty subsequences |
| Width | `max(subsequence) - min(subsequence)` |
| Modulo | `10^9 + 7` |

Function shape:

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

## Examples

Example 1:

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

The non-empty subsequences are:

| Subsequence | Width |
|---|---:|
| `[2]` | 0 |
| `[1]` | 0 |
| `[3]` | 0 |
| `[2,1]` | 1 |
| `[2,3]` | 1 |
| `[1,3]` | 2 |
| `[2,1,3]` | 2 |

Total:

```text
0 + 0 + 0 + 1 + 1 + 2 + 2 = 6
```

Example 2:

```text
Input: nums = [2]
Output: 0
```

There is only one non-empty subsequence:

```text
[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:

```text
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:

```python
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:

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

Each of those earlier elements may be included or excluded.

So `nums[i]` is the maximum in:

```text
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:

```text
2^(n - i - 1)
```

subsequences.

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

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

Add this for every index.

## Algorithm

Sort `nums`.

Precompute powers of two modulo `MOD`:

```python
pow2[i] = 2^i % MOD
```

Then for each index `i`:

1. Add its contribution as maximum:

```python
nums[i] * pow2[i]
```

2. Subtract its contribution as minimum:

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

Return the answer modulo `MOD`.

## Walkthrough

Use:

```text
nums = [2, 1, 3]
```

After sorting:

```text
[1, 2, 3]
```

Powers of two:

| `i` | `2^i` |
|---|---:|
| 0 | 1 |
| 1 | 2 |
| 2 | 4 |

Contribution by index:

| `i` | `nums[i]` | As max | As min | Net |
|---|---:|---:|---:|---:|
| 0 | 1 | `1 * 1 = 1` | `1 * 4 = 4` | -3 |
| 1 | 2 | `2 * 2 = 4` | `2 * 2 = 4` | 0 |
| 2 | 3 | `3 * 4 = 12` | `3 * 1 = 3` | 9 |

Total:

```text
-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:

```text
n = len(nums)
```

| Metric | Value | Why |
|---|---|---|
| Time | `O(n log n)` | Sorting dominates |
| Space | `O(n)` | The powers of two array uses linear space |

## Implementation

```python
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:

```python
nums.sort()
```

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

Then we precompute powers of two:

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

For each element:

```python
for i, value in enumerate(nums):
```

it contributes positively when it is a maximum:

```python
as_max = value * pow2[i]
```

and negatively when it is a minimum:

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

We add the net contribution:

```python
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:

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

Code:

```python
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

```python
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:

| Test | Why |
|---|---|
| `[2,1,3]` | Standard example |
| `[2]` | Single subsequence has width `0` |
| `[1,2]` | One nonzero pair width |
| `[1,1,1]` | All subsequences have width `0` |
| `[1,2,3,4]` | Checks multiple contribution counts |