# Sum of Subsequence Widths
**Difficulty:** HARD
[External](https://leetcode.com/problems/sum-of-subsequence-widths)
Canonical: https://scaleengineer.com/dsa/problems/sum-of-subsequence-widths
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Algorithms:** [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array
---
## 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** `109 + 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]`.

**Example 1:**

**Input:** nums = [2,1,3]
**Output:** 6
Explanation: 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

**Constraints:**

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

# Approaches
## Brute Force by Generating All Subsequences
This approach involves generating every possible non-empty subsequence of the given array. For each subsequence, we find its maximum and minimum elements, calculate the width (max - min), and add it to a running total. This is the most straightforward but also the most inefficient method, as the number of subsequences grows exponentially with the size of the input array.
**Time:** O(n * 2^n). There are `2^n` subsequences in total. For each subsequence, finding the minimum and maximum can take up to O(n) time. This makes the approach infeasible for `n > 20`. · **Space:** O(n), where n is the number of elements in `nums`. This space is used by the recursion stack and to store the current subsequence being built, both of which can go up to a depth/size of `n`.
**Pros:** Simple to understand and conceptualize.
**Cons:** Extremely inefficient due to its exponential time complexity.; Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
### Explanation
The core of this method is a backtracking algorithm to explore all possibilities of forming a subsequence. We can define a recursive helper function that builds subsequences. At each step `i` in the input array `nums`, we decide whether to include `nums[i]` in the current subsequence or not. This creates a decision tree of `2^n` paths, where `n` is the length of `nums`, with each path corresponding to a unique subsequence. Once a full subsequence is formed (i.e., we've made a decision for every element), we check if it's non-empty. If it is, we iterate through it to find the minimum and maximum values, compute their difference, and add this width to a global sum. All additions are performed modulo `10^9 + 7` to prevent overflow and meet the problem's requirements.

```java
class Solution {
    long totalWidth = 0;
    int MOD = 1_000_000_007;

    public int sumSubsequenceWidths(int[] nums) {
        // Note: This approach is too slow and will time out.
        findSubsequences(nums, 0, new java.util.ArrayList<>());
        return (int) totalWidth;
    }

    private void findSubsequences(int[] nums, int index, java.util.List<Integer> currentSubsequence) {
        if (index == nums.length) {
            if (!currentSubsequence.isEmpty()) {
                int minVal = Integer.MAX_VALUE;
                int maxVal = Integer.MIN_VALUE;
                for (int num : currentSubsequence) {
                    minVal = Math.min(minVal, num);
                    maxVal = Math.max(maxVal, num);
                }
                totalWidth = (totalWidth + maxVal - minVal) % MOD;
            }
            return;
        }

        // Decision 1: Exclude nums[index]
        findSubsequences(nums, index + 1, currentSubsequence);

        // Decision 2: Include nums[index]
        currentSubsequence.add(nums[index]);
        findSubsequences(nums, index + 1, currentSubsequence);
        currentSubsequence.remove(currentSubsequence.size() - 1); // Backtrack
    }
}
```
### Algorithm
- Initialize a global variable `totalWidth` to 0.
- Create a recursive function, say `findSubsequences(index, currentSubsequence)`, to generate all subsequences.
- **Base Case:** When the `index` reaches the end of the array:
  - If the `currentSubsequence` is not empty, find its minimum and maximum elements.
  - Calculate the width (`max - min`).
  - Add the width to `totalWidth`, taking modulo `10^9 + 7`.
  - Return.
- **Recursive Step:** For each element `nums[index]`, make two recursive calls:
  1. One call that excludes `nums[index]` from the subsequence: `findSubsequences(index + 1, currentSubsequence)`.
  2. One call that includes `nums[index]`: add `nums[index]` to `currentSubsequence`, call `findSubsequences(index + 1, currentSubsequence)`, and then remove it to backtrack.
- Start the process by calling `findSubsequences(0, new ArrayList<>())`.
- Return the final `totalWidth`.

## Mathematical Approach with Sorting and Precomputation
A more efficient approach avoids generating subsequences. Instead, we can change the perspective: for each element `nums[i]`, how much does it contribute to the total sum of widths? The total sum is `(Sum of maximums of all subsequences) - (Sum of minimums of all subsequences)`. By sorting the array first, we can easily count how many times each element `nums[i]` acts as a maximum or a minimum in a subsequence.
**Time:** O(n log n). Sorting the array takes `O(n log n)`. Precomputing powers and the final summation loop both take `O(n)`. The sorting step dominates the complexity. · **Space:** O(n). We need an array of size `n` to store the precomputed powers of 2. The space for sorting can also be up to `O(n)` depending on the implementation (e.g., TimSort in Java).
**Pros:** Significantly faster than brute force with a polynomial time complexity.; Passes for the given constraints.
**Cons:** Requires O(n) extra space to store the precomputed powers of 2.
### Explanation
After sorting the array `nums`, let's consider an element `nums[i]`. 
For `nums[i]` to be the maximum element of a subsequence, that subsequence must contain `nums[i]`, and all its other elements must be chosen from the set of elements smaller than or equal to `nums[i]`, which are `{nums[0], nums[1], ..., nums[i-1]}`. There are `i` such elements, and they can be chosen in `2^i` ways (the number of subsets). Thus, `nums[i]` contributes `nums[i] * 2^i` to the total sum of maximums.
Similarly, for `nums[i]` to be the minimum element, all other elements must be chosen from `{nums[i+1], ..., nums[n-1]}`. There are `n-1-i` such elements, leading to `2^(n-1-i)` subsequences where `nums[i]` is the minimum. Its contribution to the total sum of minimums is `nums[i] * 2^(n-1-i)`.
The final answer is the sum of all `nums[i] * 2^i` minus the sum of all `nums[i] * 2^(n-1-i)`. To implement this efficiently, we can precompute all necessary powers of 2.

```java
import java.util.Arrays;

class Solution {
    public int sumSubsequenceWidths(int[] nums) {
        int n = nums.length;
        int MOD = 1_000_000_007;

        Arrays.sort(nums);

        long[] pows = new long[n];
        pows[0] = 1;
        for (int i = 1; i < n; i++) {
            pows[i] = (pows[i - 1] * 2) % MOD;
        }

        long sumMax = 0;
        long sumMin = 0;

        for (int i = 0; i < n; i++) {
            sumMax = (sumMax + (long)nums[i] * pows[i]) % MOD;
            sumMin = (sumMin + (long)nums[i] * pows[n - 1 - i]) % MOD;
        }

        long result = (sumMax - sumMin + MOD) % MOD;
        return (int) result;
    }
}
```
### Algorithm
- First, sort the input array `nums` in non-decreasing order.
- The total sum of widths can be expressed as `(Sum of all maximums) - (Sum of all minimums)`.
- Precompute powers of 2 modulo `10^9 + 7`. Create an array `pows` where `pows[i] = 2^i % MOD`.
- Initialize `sumMax = 0` and `sumMin = 0`.
- Iterate through the sorted array from `i = 0` to `n-1`:
  - An element `nums[i]` will be the maximum in `2^i` subsequences. Add `nums[i] * pows[i]` to `sumMax`.
  - An element `nums[i]` will be the minimum in `2^(n-1-i)` subsequences. Add `nums[i] * pows[n-1-i]` to `sumMin`.
- The final result is `(sumMax - sumMin + MOD) % MOD`.

## Optimized Mathematical Approach with Constant Space
This approach builds upon the previous mathematical insight but optimizes the calculation to reduce space complexity. By rearranging the summation formula, we can avoid precomputing and storing all powers of 2, leading to a constant space solution (excluding the space used for sorting).
**Time:** O(n log n). Dominated by the initial sort. The subsequent loop runs in `O(n)` time. · **Space:** O(log n) or O(n). This is the space used by the sorting algorithm itself (e.g., `O(log n)` for Quicksort's recursion stack, `O(n)` for Mergesort). Apart from that, the algorithm uses only O(1) extra space.
**Pros:** Most efficient in terms of both time and space.; Elegant and concise implementation.
**Cons:** The mathematical derivation is less direct and might be harder to come up with during an interview.
### Explanation
We start with the formula derived in the previous approach: `Sum = sum(nums[i] * 2^i) - sum(nums[i] * 2^(n-1-i))`. Let's manipulate the second sum by changing the index of summation. If we let `j = n-1-i`, as `i` goes from `0` to `n-1`, `j` goes from `n-1` to `0`. The second sum becomes `sum_{j=0}^{n-1} (nums[n-1-j] * 2^j)`. Now we can combine the two sums:
`Sum = sum_{i=0}^{n-1} (nums[i] * 2^i) - sum_{i=0}^{n-1} (nums[n-1-i] * 2^i)`
`Sum = sum_{i=0}^{n-1} (nums[i] - nums[n-1-i]) * 2^i`
This elegant formula allows us to compute the total sum in a single loop after sorting. We can maintain a variable `p` for the power of 2, initializing it to `1` (`2^0`) and doubling it in each iteration. This eliminates the need for the `O(n)` space power array.

```java
import java.util.Arrays;

class Solution {
    public int sumSubsequenceWidths(int[] nums) {
        int n = nums.length;
        int MOD = 1_000_000_007;

        Arrays.sort(nums);

        long totalWidth = 0;
        long p = 1; // Represents 2^i

        for (int i = 0; i < n; i++) {
            // Calculate (nums[i] - nums[n-1-i]) * p
            // We do this by adding the positive part and subtracting the negative part
            // to handle modulo arithmetic correctly.
            totalWidth = (totalWidth + (long)nums[i] * p) % MOD;
            totalWidth = (totalWidth - (long)nums[n - 1 - i] * p + MOD) % MOD;
            p = (p * 2) % MOD;
        }

        return (int) totalWidth;
    }
}
```
### Algorithm
- First, sort the input array `nums`.
- The total width sum can be simplified to the formula: `Sum = sum_{i=0}^{n-1} (nums[i] - nums[n-1-i]) * 2^i`.
- Initialize `totalWidth = 0` and `p = 1` (where `p` will represent `2^i`).
- Iterate from `i = 0` to `n-1`:
  - Calculate the current term: `term = (nums[i] - nums[n-1-i]) * p`.
  - Add this term to `totalWidth`, ensuring all calculations are done modulo `10^9 + 7`.
  - Update `p` for the next iteration: `p = p * 2`.
- Return the final `totalWidth` after adjusting for any negative results from the modulo operations.

# Solutions
### Java

```java
class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int sumSubseqWidths ( int [] nums ) { Arrays . sort ( nums ); long ans = 0 , p = 1 ; int n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { ans = ( ans + ( nums [ i ] - nums [ n - i - 1 ]) * p + MOD ) % MOD ; p = ( p << 1 ) % MOD ; } return ( int ) ans ; } }
```

### CPP

```cpp
class Solution { public: const int mod = 1e9 + 7 ; int sumSubseqWidths ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); long ans = 0 , p = 1 ; int n = nums . size (); for ( int i = 0 ; i < n ; ++ i ) { ans = ( ans + ( nums [ i ] - nums [ n - i - 1 ]) * p + mod ) % mod ; p = ( p << 1 ) % mod ; } return ans ; } };
```

### Python

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