Sum of Subsequence Widths
HardPrompt
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] <= 105
Approaches
3 approaches with complexity analysis and trade-offs.
This approach involves generating every possible non-empty subsequence of the given array. For each subsequence, we find its maximum and minimum elements, calculate the width (max - min), and add it to a running total. This is the most straightforward but also the most inefficient method, as the number of subsequences grows exponentially with the size of the input array.
Algorithm
- Initialize a global variable
totalWidthto 0. - Create a recursive function, say
findSubsequences(index, currentSubsequence), to generate all subsequences. - Base Case: When the
indexreaches the end of the array:- If the
currentSubsequenceis not empty, find its minimum and maximum elements. - Calculate the width (
max - min). - Add the width to
totalWidth, taking modulo10^9 + 7. - Return.
- If the
- Recursive Step: For each element
nums[index], make two recursive calls:- One call that excludes
nums[index]from the subsequence:findSubsequences(index + 1, currentSubsequence). - One call that includes
nums[index]: addnums[index]tocurrentSubsequence, callfindSubsequences(index + 1, currentSubsequence), and then remove it to backtrack.
- One call that excludes
- Start the process by calling
findSubsequences(0, new ArrayList<>()). - Return the final
totalWidth.
Walkthrough
The core of this method is a backtracking algorithm to explore all possibilities of forming a subsequence. We can define a recursive helper function that builds subsequences. At each step i in the input array nums, we decide whether to include nums[i] in the current subsequence or not. This creates a decision tree of 2^n paths, where n is the length of nums, with each path corresponding to a unique subsequence. Once a full subsequence is formed (i.e., we've made a decision for every element), we check if it's non-empty. If it is, we iterate through it to find the minimum and maximum values, compute their difference, and add this width to a global sum. All additions are performed modulo 10^9 + 7 to prevent overflow and meet the problem's requirements.
class Solution { long totalWidth = 0; int MOD = 1_000_000_007; public int sumSubsequenceWidths(int[] nums) { // Note: This approach is too slow and will time out. findSubsequences(nums, 0, new java.util.ArrayList<>()); return (int) totalWidth; } private void findSubsequences(int[] nums, int index, java.util.List<Integer> currentSubsequence) { if (index == nums.length) { if (!currentSubsequence.isEmpty()) { int minVal = Integer.MAX_VALUE; int maxVal = Integer.MIN_VALUE; for (int num : currentSubsequence) { minVal = Math.min(minVal, num); maxVal = Math.max(maxVal, num); } totalWidth = (totalWidth + maxVal - minVal) % MOD; } return; } // Decision 1: Exclude nums[index] findSubsequences(nums, index + 1, currentSubsequence); // Decision 2: Include nums[index] currentSubsequence.add(nums[index]); findSubsequences(nums, index + 1, currentSubsequence); currentSubsequence.remove(currentSubsequence.size() - 1); // Backtrack }}Complexity
Time
O(n * 2^n). There are `2^n` subsequences in total. For each subsequence, finding the minimum and maximum can take up to O(n) time. This makes the approach infeasible for `n > 20`.
Space
O(n), where n is the number of elements in `nums`. This space is used by the recursion stack and to store the current subsequence being built, both of which can go up to a depth/size of `n`.
Trade-offs
Pros
Simple to understand and conceptualize.
Cons
Extremely inefficient due to its exponential time complexity.
Will result in a 'Time Limit Exceeded' (TLE) error for the given constraints.
A more efficient approach avoids generating subsequences. Instead, we can change the perspective: for each element nums[i], how much does it contribute to the total sum of widths? The total sum is (Sum of maximums of all subsequences) - (Sum of minimums of all subsequences). By sorting the array first, we can easily count how many times each element nums[i] acts as a maximum or a minimum in a subsequence.
Algorithm
- First, sort the input array
numsin non-decreasing order. - The total sum of widths can be expressed as
(Sum of all maximums) - (Sum of all minimums). - Precompute powers of 2 modulo
10^9 + 7. Create an arraypowswherepows[i] = 2^i % MOD. - Initialize
sumMax = 0andsumMin = 0. - Iterate through the sorted array from
i = 0ton-1:- An element
nums[i]will be the maximum in2^isubsequences. Addnums[i] * pows[i]tosumMax. - An element
nums[i]will be the minimum in2^(n-1-i)subsequences. Addnums[i] * pows[n-1-i]tosumMin.
- An element
- The final result is
(sumMax - sumMin + MOD) % MOD.
Walkthrough
After sorting the array nums, let's consider an element nums[i].
For nums[i] to be the maximum element of a subsequence, that subsequence must contain nums[i], and all its other elements must be chosen from the set of elements smaller than or equal to nums[i], which are {nums[0], nums[1], ..., nums[i-1]}. There are i such elements, and they can be chosen in 2^i ways (the number of subsets). Thus, nums[i] contributes nums[i] * 2^i to the total sum of maximums.
Similarly, for nums[i] to be the minimum element, all other elements must be chosen from {nums[i+1], ..., nums[n-1]}. There are n-1-i such elements, leading to 2^(n-1-i) subsequences where nums[i] is the minimum. Its contribution to the total sum of minimums is nums[i] * 2^(n-1-i).
The final answer is the sum of all nums[i] * 2^i minus the sum of all nums[i] * 2^(n-1-i). To implement this efficiently, we can precompute all necessary powers of 2.
import java.util.Arrays; class Solution { public int sumSubsequenceWidths(int[] nums) { int n = nums.length; int MOD = 1_000_000_007; Arrays.sort(nums); long[] pows = new long[n]; pows[0] = 1; for (int i = 1; i < n; i++) { pows[i] = (pows[i - 1] * 2) % MOD; } long sumMax = 0; long sumMin = 0; for (int i = 0; i < n; i++) { sumMax = (sumMax + (long)nums[i] * pows[i]) % MOD; sumMin = (sumMin + (long)nums[i] * pows[n - 1 - i]) % MOD; } long result = (sumMax - sumMin + MOD) % MOD; return (int) result; }}Complexity
Time
O(n log n). Sorting the array takes `O(n log n)`. Precomputing powers and the final summation loop both take `O(n)`. The sorting step dominates the complexity.
Space
O(n). We need an array of size `n` to store the precomputed powers of 2. The space for sorting can also be up to `O(n)` depending on the implementation (e.g., TimSort in Java).
Trade-offs
Pros
Significantly faster than brute force with a polynomial time complexity.
Passes for the given constraints.
Cons
Requires O(n) extra space to store the precomputed powers of 2.
This approach builds upon the previous mathematical insight but optimizes the calculation to reduce space complexity. By rearranging the summation formula, we can avoid precomputing and storing all powers of 2, leading to a constant space solution (excluding the space used for sorting).
Algorithm
- First, sort the input array
nums. - The total width sum can be simplified to the formula:
Sum = sum_{i=0}^{n-1} (nums[i] - nums[n-1-i]) * 2^i. - Initialize
totalWidth = 0andp = 1(wherepwill represent2^i). - Iterate from
i = 0ton-1:- Calculate the current term:
term = (nums[i] - nums[n-1-i]) * p. - Add this term to
totalWidth, ensuring all calculations are done modulo10^9 + 7. - Update
pfor the next iteration:p = p * 2.
- Calculate the current term:
- Return the final
totalWidthafter adjusting for any negative results from the modulo operations.
Walkthrough
We start with the formula derived in the previous approach: Sum = sum(nums[i] * 2^i) - sum(nums[i] * 2^(n-1-i)). Let's manipulate the second sum by changing the index of summation. If we let j = n-1-i, as i goes from 0 to n-1, j goes from n-1 to 0. The second sum becomes sum_{j=0}^{n-1} (nums[n-1-j] * 2^j). Now we can combine the two sums:
Sum = sum_{i=0}^{n-1} (nums[i] * 2^i) - sum_{i=0}^{n-1} (nums[n-1-i] * 2^i)
Sum = sum_{i=0}^{n-1} (nums[i] - nums[n-1-i]) * 2^i
This elegant formula allows us to compute the total sum in a single loop after sorting. We can maintain a variable p for the power of 2, initializing it to 1 (2^0) and doubling it in each iteration. This eliminates the need for the O(n) space power array.
import java.util.Arrays; class Solution { public int sumSubsequenceWidths(int[] nums) { int n = nums.length; int MOD = 1_000_000_007; Arrays.sort(nums); long totalWidth = 0; long p = 1; // Represents 2^i for (int i = 0; i < n; i++) { // Calculate (nums[i] - nums[n-1-i]) * p // We do this by adding the positive part and subtracting the negative part // to handle modulo arithmetic correctly. totalWidth = (totalWidth + (long)nums[i] * p) % MOD; totalWidth = (totalWidth - (long)nums[n - 1 - i] * p + MOD) % MOD; p = (p * 2) % MOD; } return (int) totalWidth; }}Complexity
Time
O(n log n). Dominated by the initial sort. The subsequent loop runs in `O(n)` time.
Space
O(log n) or O(n). This is the space used by the sorting algorithm itself (e.g., `O(log n)` for Quicksort's recursion stack, `O(n)` for Mergesort). Apart from that, the algorithm uses only O(1) extra space.
Trade-offs
Pros
Most efficient in terms of both time and space.
Elegant and concise implementation.
Cons
The mathematical derivation is less direct and might be harder to come up with during an interview.
Solutions
Solution
class Solution { private static final int MOD = ( int ) 1 e9 + 7 ; public int sumSubseqWidths ( int [] nums ) { Arrays . sort ( nums ); long ans = 0 , p = 1 ; int n = nums . length ; for ( int i = 0 ; i < n ; ++ i ) { ans = ( ans + ( nums [ i ] - nums [ n - i - 1 ]) * p + MOD ) % MOD ; p = ( p << 1 ) % MOD ; } return ( int ) ans ; } }class Solution { public: const int mod = 1e9 + 7 ; int sumSubseqWidths ( vector < int >& nums ) { sort ( nums . begin (), nums . end ()); long ans = 0 , p = 1 ; int n = nums . size (); for ( int i = 0 ; i < n ; ++ i ) { ans = ( ans + ( nums [ i ] - nums [ n - i - 1 ]) * p + mod ) % mod ; p = ( p << 1 ) % mod ; } return ans ; } };class Solution : def sumSubseqWidths ( self , nums : List [ int ]) -> int : mod = 10 ** 9 + 7 nums . sort () ans , p = 0 , 1 for i , v in enumerate ( nums ): ans = ( ans + ( v - nums [ - i - 1 ]) * p ) % mod p = ( p << 1 ) % mod return ansVideo walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.