Sum of Subsequence Widths — LeetCode 891 Python Solution

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

Example

Input

nums = [2,1,3]

Output

6

Explanation

The subsequences are [1], [2], [3], [2,1], [2,3], [1,3], [2,1,3].

Python solution

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

Complexity

Pattern: Sorting

Spend O(n log n) once to buy an ordering that makes the rest of the problem trivial. LeetCode 891. Sum of Subsequence Widths is filed here because LeetCode tags it Sorting, which is the vocabulary this hub collects.

The sorting guide has the Python template for the pattern and the 401 LeetCode problems that use it.

Related problems