Sum of Subsequence Widths solution and explanation
5 more videos on this problem
花花酱 LeetCode 891. Sum of Subsequence Widths - 刷题找工作 EP218Hua Hua · 13:53 · 1K views
LeetCode 891 | Sum of Subsequence Widths | Bruteforce and Optimised Algo | Ninjas World | PlacementsSkills4U · 26:50 · 399 views
【每日一题】891. Sum of Subsequence Widths, 1/8/2020Huifeng Guan · 20:43 · 249 views
Leetcode 891. Sum of Subsequence Widths (quick power)LetsCode · 11:51 · 150 views
No Sound Leetcode 891: Sum of Subsequence WidthsExtremeProgrammer · 1:48 · 22 views
LeetCode 891: Sum of Subsequence WidthsAlitaCode · 29:19 · 4 views
The problem
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.
Approach 1: Efficient Using Sorting and Powers of Two
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.
class Solution:
def sumSubseqWidths(self, nums):
MOD = 10**9 + 7
n = len(nums)
nums.sort()
pow2 = [1]
for i in range(1, n):
pow2.append(pow2[-1] * 2 % MOD)
result = 0
for i in range(n):
result = (result + nums[i] * (pow2[i] - pow2[n - 1 - i])) % MOD
return result#include <vector>
#include <algorithm>
using namespace std;
class Solution {
public:
int sumSubseqWidths(vector<int>& nums) {
sort(nums.begin(), nums.end());
long mod = 1e9 + 7, x = 0, n = nums.size(), pow2 = 1;
vector<long> pow2Arr(n, 1);
for (int i = 1; i < n; ++i)
pow2Arr[i] = (pow2Arr[i - 1] * 2) % mod;
for (int i = 0; i < n; ++i) {
x = (x + nums[i] * (pow2Arr[i] - pow2Arr[n - 1 - i])) % mod;
}
return (int)x;
}
};var sumSubseqWidths = function(nums) {
const MOD = 1e9 + 7;
nums.sort((a, b) => a - b);
const n = nums.length;
let pow2 = new Array(n).fill(1);
for (let i = 1; i < n; i++) {
pow2[i] = pow2[i - 1] * 2 % MOD;
}
let result = 0;
for (let i = 0; i < n; i++) {
result = (result + nums[i] * (pow2[i] - pow2[n - 1 - i])) % MOD;
}
return result;
};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.
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 2: Default Approach
class Solution {
private static final int MOD = (int) 1e9 + 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;
}
}func sumSubseqWidths(nums []int) (ans int) {
const mod int = 1e9 + 7
sort.Ints(nums)
p, n := 1, len(nums)
for i, v := range nums {
ans = (ans + (v-nums[n-i-1])*p + mod) % mod
p = (p << 1) % mod
}
return
}Complexity comparison
| 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 | – |
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 |
Frequently asked questions
Is Sum of Subsequence Widths easy or hard?
LeetCode classifies this problem as Hard because the key idea is not obvious. The difficulty comes from recognizing that each element's contribution can be counted mathematically instead of enumerating all subsequences.
Sum of Subsequence Widths Python/Java solution
Most implementations sort the array, precompute powers of two modulo 1e9+7, and iterate through the array adding nums[i] * (2^i - 2^(n-i-1)). The same logic works in Python, Java, C++, and JavaScript with minor syntax differences.
How to solve Sum of Subsequence Widths in O(n)?
Pure O(n) is not achievable unless the input is already sorted. With a sorted array, you can compute powers of two and accumulate contributions in a single linear pass. Each element contributes based on how many subsequences treat it as a maximum versus a minimum.
What is the best approach for Sum of Subsequence Widths?
The optimal approach sorts the array and counts how many times each element appears as the minimum and maximum in subsequences. After sorting, an element at index i contributes nums[i] * (2^i - 2^(n-i-1)). This converts an exponential enumeration problem into an O(n log n) solution due to sorting.
Is Sum of Subsequence Widths asked at Google/Amazon/Meta?
This problem reflects the style of algorithmic questions commonly asked at companies like Google, Amazon, and Meta because it combines sorting, combinatorics, and contribution counting. Variants involving subsequence counting and mathematical reasoning appear frequently in senior-level interviews.
What data structure is used in Sum of Subsequence Widths?
The solution mainly relies on arrays. The algorithm sorts the array and uses another array (or variables) to store powers of two for combinatorial counting. No advanced data structures are required beyond basic array operations.
What is the time complexity of Sum of Subsequence Widths?
The optimal solution runs in O(n log n) time because the array must be sorted first. After sorting, a single pass computes each element's contribution using precomputed powers of two. Space complexity is O(n) for the power array.