Sum of Subarray Minimums
Solve and submit on LeetCode to build your LeetCode profile. Use the hints here when you need guidance.
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)
