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.
1var sumSubseqWidths = function(nums) {
2 const MOD = 1e9 + 7;
3 nums.sort((a, b) => a - b);
4 const n = nums.length;
5 let pow2 = new Array(n).fill(1);
6 for (let i = 1; i < n; i++) {
7 pow2[i] = pow2[i - 1] * 2 % MOD;
8 }
9 let result = 0;
10 for (let i = 0; i < n; i++) {
11 result = (result + nums[i] * (pow2[i] - pow2[n - 1 - i])) % MOD;
12 }
13 return result;
14};JavaScript provides optimal performance with native array methods. We sort the input nums array and prepare a power of two array for more efficient iteration. For each element, the difference between its potential as a maximum and a minimum is calculated and accumulated into a result, considering the modular constraint.