891. Sum of Subsequence Widths LeetCode Solution

In this guide, you will get 891. Sum of Subsequence Widths LeetCode Solution with the best time and space complexity. The solution to Sum of Subsequence Widths problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Sum of Subsequence Widths solution in C++
Sum of Subsequence Widths solution in Java
Sum of Subsequence Widths solution in Python
Additional Resources

891. Sum of Subsequence Widths LeetCode Solution image

Problem Statement of Sum of Subsequence Widths

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

Complexity Analysis

Time Complexity: O(\texttt{sort})
Space Complexity: O(\texttt{sort})

891. Sum of Subsequence Widths LeetCode Solution in C++

class Solution {
 public:
  int sumSubseqWidths(vector<int>& nums) {
    constexpr int kMod = 1'000'000'007;
    const int n = nums.size();
    long ans = 0;
    long exp = 1;

    ranges::sort(nums);

    for (int i = 0; i < n; ++i, exp = exp * 2 % kMod) {
      ans += (nums[i] - nums[n - 1 - i]) * exp;
      ans %= kMod;
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

891. Sum of Subsequence Widths LeetCode Solution in Java

class Solution {
  public int sumSubseqWidths(int[] nums) {
    final int kMod = 1_000_000_007;
    final int n = nums.length;
    long ans = 0;
    long exp = 1;

    Arrays.sort(nums);

    for (int i = 0; i < n; ++i, exp = exp * 2 % kMod) {
      ans += (nums[i] - nums[n - 1 - i]) * exp;
      ans %= kMod;
    }

    return (int) ans;
  }
}
// code provided by PROGIEZ

891. Sum of Subsequence Widths LeetCode Solution in Python

class Solution:
  def sumSubseqWidths(self, nums: list[int]) -> int:
    kMod = 1_000_000_007
    n = len(nums)
    ans = 0
    exp = 1

    nums.sort()

    for i in range(n):
      ans += (nums[i] - nums[n - 1 - i]) * exp
      ans %= kMod
      exp = exp * 2 % kMod

    return ans
 # code by PROGIEZ