DSA problem
Sum of Subarray Minimums
Given an integer array arr, return the sum of min(b) over every contiguous subarray b of arr. Because the answer can be very large, return it modulo 10⁹ + 7.
The brute force enumerates all O(n²) subarrays and takes the min of each in O(n), giving O(n³). Using a sliding minimum it drops to O(n²), but even that is too slow for n up to 3 * 10⁴.
The classic trick is to flip the question: instead of asking "what is the min of each subarray?", ask "how many subarrays does each element minimise?". For each arr[i], count the number of subarrays in which arr[i] is the minimum value; the total contribution is then arr[i] * count.
For a chosen arr[i], let L be the distance to the previous strictly smaller element (or the start of the array) and R be the distance to the next less-or-equal element (or the end of the array). The number of subarrays where arr[i] is the minimum equals L * R. The asymmetry (strict vs non-strict comparison) ensures that subarrays with duplicate minima are counted exactly once. Both L and R can be computed for every index using a monotonic increasing stack, giving an O(n) algorithm overall. Apply the modulus after every multiplication and addition to avoid overflow.
Examples
arr = [3,1,2,4]17arr = [11,81,94,43,3]444arr = [1,2,3]10Constraints
- 1 <= arr.length <= 3 * 10^4
- 1 <= arr[i] <= 3 * 10^4
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.