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] <= 105Problem Overview: Given an integer array nums, compute the sum of widths of all subsequences. The width of a subsequence is defined as max(subseq) - min(subseq). Since the number of subsequences grows exponentially (2^n), generating each one directly becomes infeasible for large inputs.
Approach 1: Brute Force Subsequence Enumeration (O(n * 2^n) time, O(n) space)
Generate every subsequence using recursion or bitmasking. For each subsequence, scan its elements to determine the minimum and maximum values, then add max - min to the total. This approach makes the definition of the problem explicit and helps build intuition about how widths are calculated. However, the number of subsequences is 2^n, so even moderate input sizes become impractical. This method mainly serves as a conceptual baseline before applying mathematical insights.
Approach 2: Sorting + Contribution Counting with Powers of Two (O(n log n) time, O(n) space)
The optimal approach avoids enumerating subsequences. Instead, count how often each element contributes as a minimum or maximum. Start by sorting the array using sorting. After sorting, for an element at index i, there are 2^i subsequences where it becomes the maximum (choose any subset of elements before it) and 2^(n-i-1) subsequences where it becomes the minimum (choose any subset of elements after it).
This observation converts the problem into a contribution formula. Each element contributes:
nums[i] * (2^i - 2^(n-i-1))
The term 2^i counts how many subsequences treat the value as the maximum, while 2^(n-i-1) counts how many treat it as the minimum. Precompute powers of two using modular arithmetic to avoid overflow. Iterate once through the sorted array and accumulate contributions. The heavy lifting here comes from recognizing the combinatorial pattern rather than generating subsequences explicitly.
This technique blends ideas from array manipulation, combinatorics, and math. Sorting ensures elements to the left are always smaller and elements to the right are always larger, which makes the contribution counting valid.
Recommended for interviews: The sorting + powers-of-two contribution approach is the expected solution. It demonstrates that you can transform an exponential subsequence problem into a linear pass after sorting. Mentioning the brute force approach briefly shows you understand the baseline complexity, but implementing the contribution formula shows strong algorithmic reasoning and familiarity with combinatorial counting.
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.
First, 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.
Python
C++
JavaScript
Time Complexity: O(n log n) due to sorting, followed by O(n) for calculation.
Space Complexity: O(n) for storing powers of two.
| Approach | Complexity |
|---|---|
| Efficient Using Sorting and Powers of Two | Time Complexity: O(n log n) due to sorting, followed by O(n) for calculation. |
| Default Approach | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Subsequence Enumeration | O(n * 2^n) | O(n) | Useful for understanding the definition of subsequence widths or verifying logic on very small inputs |
| Sorting + Powers of Two Contribution | O(n log n) | O(n) | Optimal solution for interviews and production; avoids generating subsequences by counting element contributions |
花花酱 LeetCode 891. Sum of Subsequence Widths - 刷题找工作 EP218 • Hua Hua • 1,471 views views
Watch 9 more video solutions →Practice Sum of Subsequence Widths with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor