Leetcode: 891. Sum of Subsequence Widths

Pattern: Compute value for all subsequences of an array. Sort the array and compute how many time each element appear as the minimum and maximum in all subsequences. Time complexity is \(O(n)\) with space \(O(1)\).

from typing import List


class Solution:
    def sumSubseqWidths(self, nums: List[int]) -> int:
        N = len(nums)
        MOD = 10**9 + 7
        nums.sort()

        mins = 0
        maxs = 0
        p = 1
        for i in range(N):
            mins = (mins + nums[N - i - 1] * p) % MOD
            maxs = (maxs + nums[i] * p) % MOD
            p = (p * 2) % MOD

        return (maxs - mins + MOD) % MOD