Frontend School

Subarray Minimum Weighted Sum

DSA
hard

Subarray Minimum Weighted Sum

Hard
Monotonic Stack
Arrays
Prefix Sum
Mathematics

Overview

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.

What you need to do / Task

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):

  1. Identify all contiguous subarrays nums[k...j] such that 0 <= k <= i <= j < n and nums[i] is the minimum value in nums[k...j].
  2. For each such subarray, calculate nums[i] * (j - k + 1).
  3. Sum up all these calculated values across all i, k, and j.

Input & output

  • Input: nums: number[]
    • An array of integers representing values.
  • Output: number
    • A single integer representing the total Subarray Minimum Weighted Sum, modulo 10^9 + 7.

Clarifications

  • Empty Input: The input array nums will not be empty.
  • Large Sums: Since the sum can be very large, return the result modulo 10^9 + 7.
  • Duplicates: If there are duplicate minimums in a subarray, 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

1

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.

2

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.

3

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

Constraints & assumptions

  • 1 <= nums.length <= 10^5
  • 1 <= nums[i] <= 10^9
  • The final result must be returned modulo 10^9 + 7.

Out of scope

  • Optimizing for memory beyond O(N) is not required.
  • Handling non-integer inputs or negative values in nums.

What interviewers evaluate

  • Correct application of Monotonic Stack: Ability to correctly identify and implement the use of monotonic stacks to determine the valid ranges for each element as a minimum.
  • Mathematical derivation for summation: Accuracy in deriving the formula for the sum of lengths of all valid subarrays for each nums[i] without explicit iteration.
  • Edge case handling: Correctly managing boundary conditions (e.g., elements at the start/end of the array, all elements being equal).
  • Time and Space Complexity: Achieving an optimal O(N) time complexity and O(N) space complexity.
  • Modular Arithmetic: Correctly applying modulo operations at each step to prevent integer overflow and ensure the final result is accurate.

Loading editor...