problemhardalgorithmsleetcode-891leetcode 891leetcode891

Sum of Subsequence Widths

HardUpdated: Aug 2, 2025
Practice on:
LeetCode

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 thewidths of all the non-empty subsequences of _nums. Since the answer may be very large, return it modulo 10^9 + 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].

Examples

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 <= 10^5
  • 1 <= nums[i] <= 10^5

Solution

Approach

For each number, count how many subsequences it is the maximum and how many it is the minimum. The difference gives its total contribution to the sum of widths. We sort the array and use powers of 2 to count the number of subsequences for each position.

Let nums be sorted. For each nums[i], it is the maximum in 2^i subsequences and the minimum in 2^{n-1-i} subsequences. The answer is the sum over all i of nums[i] * (2^i - 2^{n-1-i}).

Code

C++
#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
    int sumSubseqWidths(vector<int>& nums) {
        const int MOD = 1e9+7;
        int n = nums.size();
        sort(nums.begin(), nums.end());
        vector<long> pow2(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 + nums[i] * (pow2[i] - pow2[n-1-i] + MOD) % MOD) % MOD;
        }
        return (int)res;
    }
};
Java
import java.util.*;
class Solution {
    public int sumSubseqWidths(int[] nums) {
        int MOD = 1_000_000_007, n = nums.length;
        Arrays.sort(nums);
        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 + nums[i] * (pow2[i] - pow2[n-1-i] + MOD) % MOD) % MOD;
        }
        return (int)res;
    }
}
Kotlin
class Solution {
    fun sumSubseqWidths(nums: IntArray): Int {
        val MOD = 1_000_000_007L
        val n = nums.size
        nums.sort()
        val pow2 = LongArray(n)
        pow2[0] = 1L
        for (i in 1 until n) pow2[i] = pow2[i-1] * 2 % MOD
        var res = 0L
        for (i in 0 until n) {
            res = (res + nums[i] * ((pow2[i] - pow2[n-1-i] + MOD) % MOD)) % MOD
        }
        return res.toInt()
    }
}
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
        res = 0
        for i in range(n):
            res = (res + nums[i] * (pow2[i] - pow2[n-1-i])) % MOD
        return res
Rust
impl Solution {
    pub fn sum_subseq_widths(mut nums: Vec<i32>) -> i32 {
        const MOD: i64 = 1_000_000_007;
        let n = nums.len();
        nums.sort();
        let mut pow2 = vec![1i64; n];
        for i in 1..n { pow2[i] = pow2[i-1] * 2 % MOD; }
        let mut res = 0i64;
        for i in 0..n {
            res = (res + nums[i] as i64 * (pow2[i] - pow2[n-1-i] + MOD) % MOD) % MOD;
        }
        res as i32
    }
}
TypeScript
function sumSubseqWidths(nums: number[]): number {
    const MOD = 1e9 + 7;
    const n = nums.length;
    nums.sort((a, b) => a - b);
    const 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 + nums[i] * ((pow2[i] - pow2[n-1-i] + MOD) % MOD)) % MOD;
    }
    return res;
}

Complexity

  • ⏰ Time complexity: O(n log n)
  • 🧺 Space complexity: O(n)

Comments