花花酱 LeetCode 891. Sum of Subsequence Widths - 刷题找工作 EP218
Sum of Subsequence Widths - Video Solution
Watch 6 video solutions for Sum of Subsequence Widths, a hard level problem involving Array, Math, Sorting. This walkthrough by Hua Hua has 1,472 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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
Approach Overview
Problem 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.
Complexity Analysis
| 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 |