Sponsored
Sponsored
This approach involves sorting the array first. For each element in the sorted array, think of it appearing as the largest and smallest element in various subsequences. Using powers of two, we can determine the number of times an element appears as a maximum or minimum. This reduces the problem to simple arithmetic operations, making the solution efficient enough to handle large input sizes. The final result is calculated using modulo 10^9 + 7.
Time Complexity: O(n log n) due to sorting, followed by O(n) for calculation.
Space Complexity: O(n) for storing powers of two.
1class Solution:
2 def sumSubseqWidths(self, nums):
3 MOD = 10**9 + 7
4 n = len(nums)
5 nums.sort()
6 pow2 = [1]
7 for i in range(1, n):
8 pow2.append(pow2[-1] * 2 % MOD)
9 result = 0
10 for i in range(n):
11 result = (result + nums[i] * (pow2[i] - pow2[n - 1 - i])) % MOD
12 return resultFirst, we sort the array to ensure that each element's position corresponds to its natural rank in the list. We calculate powers of two up to the length of the array minus one to efficiently compute how many times each element can be a maximum or minimum. By iterating through the sorted list, we add the contribution of each element to the sum based on the number of subsequences where it's the maximum and subtract where it's the minimum. The computation is done under modulus to prevent overflow.