Watch 10 video solutions for Sum of Subarray Minimums, a medium level problem involving Array, Dynamic Programming, Stack. This walkthrough by Fraz has 91,137 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Given an array of integers arr, find the sum of min(b), where b ranges over every (contiguous) subarray of arr. Since the answer may be large, return the answer modulo 109 + 7.
Example 1:
Input: arr = [3,1,2,4] Output: 17 Explanation: Subarrays are [3], [1], [2], [4], [3,1], [1,2], [2,4], [3,1,2], [1,2,4], [3,1,2,4]. Minimums are 3, 1, 2, 4, 1, 1, 2, 1, 1, 1. Sum is 17.
Example 2:
Input: arr = [11,81,94,43,3] Output: 444
Constraints:
1 <= arr.length <= 3 * 1041 <= arr[i] <= 3 * 104Problem Overview: Given an integer array arr, compute the sum of the minimum value of every possible subarray. A brute force enumeration would check all subarrays and track the minimum, but that becomes too slow for large inputs. The key insight is counting how many subarrays treat a specific element as the minimum.
Approach 1: Dynamic Programming with Previous Less Element (O(n) time, O(n) space)
This method combines dynamic programming with a stack that tracks the previous smaller element. For each index i, compute how many subarrays ending at i use arr[i] as the minimum. If prevLess is the nearest index to the left with a smaller value, then the contribution depends on the distance i - prevLess. A DP array stores the total contribution for subarrays ending at each index, allowing reuse of previously computed values instead of recomputing minimums. This approach reduces repeated work and builds the final answer incrementally while scanning the array once.
Approach 2: Monotonic Stack Contribution Counting (O(n) time, O(n) space)
The optimal solution uses a monotonic stack to determine the range where each element acts as the minimum. Maintain an increasing stack of indices. For every element, compute two distances: how far it can extend to the left before encountering a smaller value, and how far it can extend to the right before a strictly smaller element appears. If left represents the number of choices on the left and right on the right, the element contributes arr[i] * left * right to the total sum. Each index is pushed and popped at most once, giving linear time. This pattern appears frequently in problems involving range dominance and nearest smaller elements in an array stack workflow.
Recommended for interviews: Interviewers expect the monotonic stack solution. It demonstrates understanding of nearest-smaller-element patterns and contribution counting, both common in advanced array questions. Showing the dynamic programming interpretation first can help explain the idea, but implementing the O(n) monotonic stack approach proves you can translate the insight into an efficient solution.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Dynamic Programming with Previous Less Element | O(n) | O(n) | When explaining the incremental contribution idea or building intuition with DP relations. |
| Monotonic Stack Contribution Counting | O(n) | O(n) | Best general solution. Handles large inputs efficiently and is the expected interview approach. |