Sum of Subarray Minimums
Medium · Stack & Strings · Array · Dynamic Programming · Stack · Monotonic Stack
Problem
Given an integer array arr, consider every contiguous subarray and take its minimum element. Return the sum of all these minimums.
Because the sum can be very large, return it modulo 10^9 + 7.
Examples
Input: arr = [3,1,4,2] Output: 17
The ten subarrays have minimums 3, 1, 4, 2, 1, 1, 2, 1, 1, 1, which add up to 17.
Input: arr = [2,4,1] Output: 11
The six subarrays have minimums 2, 4, 1, 2, 1 and 1.
Input: arr = [5,5] Output: 15
The subarrays [5], [5] and [5,5] each have minimum 5.
Constraints
- 1 <= len(arr) <= 3 · 10^4
- 1 <= arr[i] <= 3 · 10^4
Approaches
- Baseline: extend every subarray — time O(n²), space O(1)
Follow-up
What if you also needed the sum of subarray maximums, or of max - min over every subarray? Run the same stack with the comparison flipped for the maximums and subtract. The first use case below asks for the maximums.
Related problems
Start free on Cariara · Coding problems · System design studio
