Code Implementation

class Solution:
    def sumSubseqWidths(self, A):
        MOD = 10 ** 9 + 7
        n = len(A)
        A.sort()
        pow2 = [1] * n
        for i in range(1, n):
            pow2[i] = pow2[i-1] * 2 % MOD
        res = 0
        for i in range(n):
            add = pow2[i] * A[i] % MOD
            sub = pow2[n-1-i] * A[i] % MOD
            res = (res + add - sub) % MOD
        return res
      

class Solution {
public:
    int sumSubseqWidths(vector<int>& A) {
        const int MOD = 1e9 + 7;
        int n = A.size();
        sort(A.begin(), A.end());
        vector<long long> pow2(n, 1);
        for (int i = 1; i < n; ++i)
            pow2[i] = pow2[i-1] * 2 % MOD;
        long long res = 0;
        for (int i = 0; i < n; ++i) {
            res = (res + pow2[i] * A[i] - pow2[n-1-i] * A[i]) % MOD;
        }
        return (res + MOD) % MOD;
    }
};
      

class Solution {
    public int sumSubseqWidths(int[] A) {
        int MOD = 1_000_000_007;
        int n = A.length;
        Arrays.sort(A);
        long[] pow2 = new long[n];
        pow2[0] = 1;
        for (int i = 1; i < n; ++i)
            pow2[i] = pow2[i-1] * 2 % MOD;
        long res = 0;
        for (int i = 0; i < n; ++i) {
            res = (res + pow2[i] * A[i] - pow2[n-1-i] * A[i]) % MOD;
        }
        return (int)((res + MOD) % MOD);
    }
}
      

var sumSubseqWidths = function(A) {
    const MOD = 1e9 + 7;
    A.sort((a, b) => a - b);
    const n = A.length;
    let pow2 = new Array(n).fill(1);
    for (let i = 1; i < n; ++i)
        pow2[i] = pow2[i-1] * 2 % MOD;
    let res = 0;
    for (let i = 0; i < n; ++i) {
        res = (res + pow2[i] * A[i] - pow2[n-1-i] * A[i]) % MOD;
    }
    return (res + MOD) % MOD;
};
      

Problem Description

Given an integer array A, you are to find the sum of the widths of all non-empty subsequences of A. The width of a subsequence is defined as the difference between its maximum and minimum element. The answer should be given modulo 10^9 + 7.

Constraints:

• 1 ≤ A.length ≤ 20000
• 1 ≤ A[i] ≤ 20000

Thought Process

At first glance, you might think about generating all possible subsequences, calculating their widths, and summing them up. However, since the number of subsequences is exponential (2ⁿ - 1), this brute-force approach is not feasible for large arrays.

We need to find an efficient way to calculate the total sum without explicitly generating every subsequence. The key insight is to realize that each element contributes to the total sum as a minimum and as a maximum in different subsequences. If we can count how many times each element serves as the minimum and maximum, we can compute the answer efficiently.

Solution Approach

Let's break down the solution step by step:

1. Sort the Array:
   • Sorting helps us easily determine which elements are smaller or larger than others.
2. Count Each Element's Contribution:
   • For each element A[i] in the sorted array:
     • It will be the maximum in 2^i subsequences (where all previous elements can be included or not).
     • It will be the minimum in 2^{n-1-i} subsequences (where all later elements can be included or not).
   • The total contribution of A[i] is:
     • A[i] * (number\_of\_times\_as\_max - number\_of\_times\_as\_min)
     • That is, A[i] * (2^i - 2^{n-1-i})
3. Sum All Contributions:
   • Iterate through the array, summing up the contributions for each element.
   • Take the answer modulo 10^9 + 7 to avoid overflow.
4. Precompute Powers of 2:
   • To efficiently calculate 2^i for all i, precompute and store them in an array.

This approach avoids generating all subsequences and instead leverages combinatorial counting and sorting to achieve efficiency.

Example Walkthrough

Let's work through an example with A = [2, 1, 3].

1. Sort the array: [1, 2, 3]
2. Precompute powers of 2: pow2 = [1, 2, 4]
3. Compute contributions:
   • For i = 0 (A[0] = 1):
     • As max: 2^0 = 1 subsequence
     • As min: 2^{2} = 4 subsequences
     • Contribution: 1 * (1 - 4) = -3
   • For i = 1 (A[1] = 2):
     • As max: 2^1 = 2
     • As min: 2^1 = 2
     • Contribution: 2 * (2 - 2) = 0
   • For i = 2 (A[2] = 3):
     • As max: 2^2 = 4
     • As min: 2^0 = 1
     • Contribution: 3 * (4 - 1) = 9
4. Sum contributions: -3 + 0 + 9 = 6
5. Final answer: 6

This matches the sum of subsequence widths for all subsequences of [2,1,3].

Time and Space Complexity

Brute-force approach:

• Would require generating all 2^n subsequences, each taking up to O(n) time to compute the width.
• Time complexity: O(n*2^n)
• Space complexity: O(2^n) if storing subsequences, otherwise O(n) for recursion stack.

• Sorting takes O(n \log n) time.
• Precomputing powers of 2 and iterating through the array are both O(n).
• Time complexity: O(n \log n)
• Space complexity: O(n) for the power array.

The optimized approach is efficient and suitable for large input sizes.

Summary

The key insight in this problem is recognizing that each element's contribution to the sum of subsequence widths can be counted combinatorially based on its position in the sorted array. By precomputing powers of 2 and leveraging sorting, we avoid brute-force enumeration and achieve an efficient solution. This approach elegantly turns an exponential problem into a polynomial one, making it feasible for large arrays.