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] <= 105This 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.
C++
JavaScript
Time Complexity: O(n log n) due to sorting, followed by O(n) for calculation.
Space Complexity: O(n) for storing powers of two.
Longest Common Subsequence - Dynamic Programming - Leetcode 1143 • NeetCode • 323,891 views views
Watch 9 more video solutions →Practice Sum of Subsequence Widths with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor