{x}
blog image

Sum of Subsequence Widths

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

Solution Explanation for Sum of Subsequence Widths

This problem asks for the sum of widths of all non-empty subsequences of a given array nums. The width of a subsequence is the difference between its maximum and minimum elements. A brute-force approach would be computationally expensive. The provided solution leverages a clever mathematical insight and sorting to achieve an efficient solution.

Core Idea:

The key observation is that for each element nums[i], its contribution to the total sum of widths depends on its position in the sorted array. Specifically, nums[i] will be the maximum element in 2^i subsequences and the minimum element in 2^(n-1-i) subsequences, where n is the length of the array.

Algorithm:

  1. Sort the array: Sort the input array nums in ascending order. This is crucial for the subsequent calculations.

  2. Iterate and accumulate: Iterate through the sorted array. For each element nums[i]:

    • Calculate its contribution to the total width: (nums[i] - nums[n - 1 - i]) * 2^i. This represents the sum of widths where nums[i] is the maximum and minimum element in its respective subsequences. The 2^i term represents the number of subsequences where nums[i] is the maximum element. Similarly, 2^(n-1-i) is the number of subsequences where nums[i] is the minimum. Since we subtract the minimum from the maximum in the calculation, we have essentially accounted for both scenarios at once.
    • Accumulate this contribution to the ans variable, ensuring to take the modulo with 10^9 + 7 to avoid integer overflow.

  3. Efficient power of 2 calculation: The code efficiently computes powers of 2 using bitwise left shift (<<). p << 1 is equivalent to p * 2.

Time and Space Complexity:

  • Time Complexity: O(n log n), dominated by the sorting step. The iteration through the sorted array takes linear time.
  • Space Complexity: O(1). The solution uses only a few variables to store intermediate results. It does not utilize extra space proportional to the input size.

Code Explanation (Python):

class Solution:
    def sumSubseqWidths(self, nums: List[int]) -> int:
        mod = 10**9 + 7
        nums.sort()
        ans, p = 0, 1  # Initialize answer and power of 2
        for i, v in enumerate(nums):
            ans = (ans + (v - nums[-i - 1]) * p) % mod  # Calculate and accumulate contribution
            p = (p << 1) % mod  # Update power of 2
        return ans

The other language versions (Java, C++, Go) follow the same algorithmic structure, differing only in syntax and specific library functions (e.g., Arrays.sort in Java vs. nums.sort() in Python). The core logic remains identical across all implementations.