Sum of Subarray Minimums
Problem
For every contiguous subarray of an integer array, take its minimum, and add all of those minimums together. Return the total modulo 10^9 + 7.
Examples
Constraints
- • 1 <= arr.length <= 3 * 10^4
- • 1 <= arr[i] <= 3 * 10^4
Hints & approach
Hint 1
Flip it: for each element, count how many subarrays have it as their minimum.
Hint 2
That count is (choices of left end) * (choices of right end).
Hint 3
Find the previous smaller and next smaller element for every index with a monotonic stack. Break ties on one side only.
Approachtry the hints first
Element arr[i] is the minimum of every subarray that starts after its previous strictly smaller element and ends before its next smaller-or-equal element. If those boundaries are at distances left[i] and right[i], arr[i] contributes arr[i] * left[i] * right[i]. Compute both distance arrays with increasing monotonic stacks, using strict comparison on one side and non-strict on the other so equal values are not double counted. Sum the contributions modulo 10^9 + 7.
Time O(n) · Space O(n)