549. Sum of Subarray Minimums
You are given an array of positive integers arr. Every contiguous, non-empty subarray of arr has a minimum element. Add up the minimum of every subarray and return the total.
Because the total can be enormous, return it modulo 10^9 + 7.
An array of length n has n·(n+1)/2 subarrays, so listing them all is only feasible for small inputs — the interesting question is how each element can know, on its own, how many subarrays it is the minimum of.
Example 1:
Input: arr = [3, 1, 2, 4]
Output: 17
Explanation: The subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4] with minimums 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Their sum is 17.
Example 2:
Input: arr = [5, 2, 2]
Output: 15
Explanation: Subarrays: [5], [2], [2], [5,2], [2,2], [5,2,2] with minimums 5, 2, 2, 2, 2, 2. Their sum is 15 — note how ties between equal elements must not double-count a subarray.
Constraints:
- 1 ≤ arr.length ≤ 3 * 10⁴
- 1 ≤ arr[i] ≤ 3 * 10⁴
- Return the answer modulo 10⁹ + 7.
Hints:
Flip the perspective: instead of asking "what is the minimum of this subarray?" for every subarray, ask "in how many subarrays is this element the minimum?" for every element. Then the answer is Σ arr[i] · count(i).
arr[i] is the minimum of exactly the subarrays that start after the previous smaller element and end before the next smaller element. If those distances are L and R, the count is L · R.
A monotonic increasing stack finds every element's previous-smaller and next-smaller neighbor in one pass each. To avoid counting a tied subarray twice, break ties one-sidedly: strictly smaller on the left, smaller-or-equal on the right.
▶ Run checks these sample cases. Submit also runs hidden edge cases.
Input: arr = [3, 1, 2, 4]
Expected output: 17