Skip to main content
Talentd

Sum of Subsequence Widths - Solution & Explanation

HardArrayMathSorting7 min read
Practice this problem

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 <= 105
  • 1 <= 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.

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.

Code

PythonC++JavaScript

Python

C++

JavaScript

Complexity

Time Complexity: O(n log n) due to sorting, followed by O(n) for calculation.
Space Complexity: O(n) for storing powers of two.

Try this approach in the editor β†’

Approach 2: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor β†’

Complexity Comparison

ApproachComplexity
Efficient Using Sorting and Powers of Two

Time Complexity: O(n log n) due to sorting, followed by O(n) for calculation.
Space Complexity: O(n) for storing powers of two.

Default Approachβ€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Brute Force Subsequence EnumerationO(n * 2^n)O(n)Useful for understanding the definition of subsequence widths or verifying logic on very small inputs
Sorting + Powers of Two ContributionO(n log n)O(n)Optimal solution for interviews and production; avoids generating subsequences by counting element contributions

Video Solution

θŠ±θŠ±ι…± LeetCode 891. Sum of Subsequence Widths - εˆ·ι’˜ζ‰Ύε·₯作 EP218 β€’ Hua Hua β€’ 1,472 views views

Watch 5 more video solutions β†’

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.

Ready to solve this problem?

Practice Sum of Subsequence Widths with our built-in code editor and test cases.

Practice on FleetCode
Previous

Two Sum

Next

Median of Two Sorted Arrays