Subarray Minimum Weighted Sum
In large-scale data processing systems, optimizing resource allocation often involves analyzing contiguous blocks of data or tasks. A common pattern is that the efficiency or cost of processing a block is determined by its smallest component, but also amplified by the block's size. This problem models such a scenario, requiring you to calculate the total weighted sum across all possible valid processing blocks, contributing to a holistic system performance metric.
You are given an array of integers nums, where nums[i] represents a certain value associated with an item at index i. Your task is to calculate the Subarray Minimum Weighted Sum. This sum is defined as the total sum of (nums[i] * length(subarray)) for all possible contiguous subarrays nums[k...j] such that nums[i] is the smallest element within that subarray nums[k...j], and k <= i <= j. The final answer should be returned modulo 10^9 + 7.
Formally, for each index i from 0 to n-1 (where n is the length of nums):
nums[k...j] such that 0 <= k <= i <= j < n and nums[i] is the minimum value in nums[k...j].nums[i] * (j - k + 1).i, k, and j.nums: number[]
number
10^9 + 7.nums will not be empty.10^9 + 7.nums[i] should be considered the unique minimum for its contribution only if it's the first occurrence of that minimum value within its valid range. To handle this, when determining the range where nums[i] is the minimum, consider L_i as the index of the previous strictly smaller element, and R_i as the index of the next smaller or equal element. This ensures each (nums[i] * length) pair is counted exactly once for the correct nums[i] as the minimum.Examples
Example 1
Input:
nums = [1, 2, 3]
Output:
15
Note:
For nums[0]=1: Subarrays where 1 is min: [1] (length=1), [1,2] (length=2), [1,2,3] (length=3). Contribution: 1*(1) + 1*(2) + 1*(3) = 6. For nums[1]=2: Subarrays where 2 is min: [2] (length=1), [2,3] (length=2). Contribution: 2*(1) + 2*(2) = 6. For nums[2]=3: Subarrays where 3 is min: [3] (length=1). Contribution: 3*(1) = 3. Total sum = 6 + 6 + 3 = 15.
Example 2
Input:
nums = [3, 1, 2, 4]
Output:
28
Note:
For nums[0]=3: The only subarray where 3 is the minimum is [3] (length=1). Contrib: 31 = 3. For nums[1]=1: The subarrays where 1 is the minimum are [3,1] (len=2), [3,1,2] (len=3), [3,1,2,4] (len=4), [1] (len=1), [1,2] (len=2), [1,2,4] (len=3). Sum of lengths = 2+3+4+1+2+3 = 15. Contrib: 115 = 15. For nums[2]=2: The subarrays where 2 is the minimum are [2] (len=1), [2,4] (len=2). Sum of lengths = 1+2 = 3. Contrib: 23 = 6. For nums[3]=4: The only subarray where 4 is the minimum is [4] (len=1). Contrib: 41 = 4. Total sum = 3 + 15 + 6 + 4 = 28.
Example 3
Input:
nums = [2, 2, 2]
Output:
20
Note:
For nums[0]=2: (L_0=-1, R_0=1). Subarray: [2] (len=1). Contrib: 21 = 2. For nums[1]=2: (L_1=-1, R_1=2). Subarrays: [2,2] (len=2), [2] (len=1). Sum of lengths = 2+1 = 3. Contrib: 23 = 6. For nums[2]=2: (L_2=-1, R_2=3). Subarrays: [2,2,2] (len=3), [2,2] (len=2), [2] (len=1). Sum of lengths = 3+2+1 = 6. Contrib: 2*6 = 12. Total sum = 2 + 6 + 12 = 20.
Constraints
1 <= nums.length <= 10^51 <= nums[i] <= 10^910^9 + 7.O(N) is not required.nums.nums[i] without explicit iteration.O(N) time complexity and O(N) space complexity.Loading editor...