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 <= 1051 <= nums[i] <= 105The key idea in #891 Sum of Subsequence Widths is to avoid generating all subsequences, since the total number of subsequences grows exponentially. Instead, observe that the width of a subsequence is defined as max - min. By sorting the array, we can determine how many times each element appears as the maximum and as the minimum across all subsequences.
After sorting, an element at index i contributes positively when it acts as the maximum and negatively when it acts as the minimum. Specifically, the number of subsequences where it is the maximum is based on how many elements exist before it, while the number of subsequences where it is the minimum depends on elements after it. Using precomputed powers of 2, we can efficiently count these combinations.
The total contribution of each element can be aggregated using modular arithmetic. Sorting enables ordered reasoning about min/max positions, resulting in an efficient O(n log n) approach with linear auxiliary calculations.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Sorting + Contribution Counting with Powers of Two | O(n log n) | O(n) |
NeetCode
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.
1#include <vector>
2#include <algorithm>
3using namespace std;
4
5class Solution {
6public:
7 int sumSubseqWidths(vector<int>& nums) {
8 sort(nums.begin(), nums.end());
9 long mod = 1e9 + 7, x = 0, n = nums.size(), pow2 = 1;
10 vector<long> pow2Arr(n, 1);
11 for (int i = 1; i < n; ++i)
12 pow2Arr[i] = (pow2Arr[i - 1] * 2) % mod;
13 for (int i = 0; i < n; ++i) {
14 x = (x + nums[i] * (pow2Arr[i] - pow2Arr[n - 1 - i])) % mod;
15 }
16 return (int)x;
17 }
18};In C++, we sort the input array to arrange each element by its relative value. We then precompute powers of two modulo 10^9 + 7 to simplify the process of calculating the resulting sum. By iterating through the sorted numbers, we determine each number's influence as a maximum and a minimum across all possible subsequences, accumulating these effects to get the final result.
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Sorting ensures that elements are processed in increasing order, which makes it easy to determine how many subsequences treat an element as the minimum or maximum. This ordered structure enables contribution counting instead of brute-force enumeration.
Yes, this problem reflects patterns commonly seen in FAANG interviews, particularly contribution techniques and combinatorial counting. It tests understanding of sorting, mathematical reasoning, and optimization beyond brute-force approaches.
The optimal approach sorts the array and calculates each element's contribution as both a maximum and a minimum across all subsequences. By using powers of two to count combinations, we avoid generating subsequences explicitly. This reduces the complexity to O(n log n).
The main techniques used are sorting and mathematical contribution counting. Precomputing powers of two helps efficiently determine how many subsequences each element participates in as a minimum or maximum.