Scale Engineer

Sum of Subsequence Widths

Hard
#0845Time: 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`.
Patterns
Math
Algorithms
Sorting
Data structures
Array

Prompt

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

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 totalWidth to 0.
  • Create a recursive function, say findSubsequences(index, currentSubsequence), to generate all subsequences.
  • Base Case: When the index reaches the end of the array:
    • If the currentSubsequence is not empty, find its minimum and maximum elements.
    • Calculate the width (max - min).
    • Add the width to totalWidth, taking modulo 10^9 + 7.
    • Return.
  • Recursive Step: For each element nums[index], make two recursive calls:
    1. One call that excludes nums[index] from the subsequence: findSubsequences(index + 1, currentSubsequence).
    2. One call that includes nums[index]: add nums[index] to currentSubsequence, call findSubsequences(index + 1, currentSubsequence), and then remove it to backtrack.
  • 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.

Solutions

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 ; } }

Video 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.

← Previous

Previous problem

Next →

Next problem