Sum of subsequence widths

Array Math Sorting

40.2% acceptance

Feb 22, 2026

736

172

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].

Solution

Rust

Time O(n log n)

Space O(1)

LeetCode

solution.rs

/*
 * 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
 */

impl Solution {
  pub fn sum_subseq_widths(mut nums: Vec<i32>) -> i32 {
    const MOD: i64 = 1_000_000_007;
    nums.sort_unstable();
    let n = nums.len();
    let mut ans = 0i64;
    let mut p = 1i64; // 2^i
    for i in 0..n {
      ans = (ans + (nums[i] as i64) * p % MOD - (nums[n - 1 - i] as i64) * p % MOD + MOD) % MOD;
      p = p * 2 % MOD;
    }
    ans as i32
  }
}