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.
The monotonic stack approach leverages a stack data structure to efficiently determine the minimum element of every subarray. By maintaining indexes and utilizing their properties, we can efficiently compute the sum of all minimum values for the contiguous subarrays.
This C solution employs a monotonically increasing stack to determine the number of elements affected by each element of the array on either side, thus calculating its contribution to the final sum.
Time Complexity: O(n), where n is the length of the array.
Space Complexity: O(n), due to the use of auxiliary arrays and a stack.
A dynamic programming approach can also be adopted to tackle the given problem. This method involves calculating the contribution of each element to subarray minimums utilizing previously calculated results intelligently.
This C solution uses an array dp to compute subarray minimum sums progressively, allowing each integer's effect to persist cumulatively across numerous subarray possibilities.
Time Complexity: O(n)
Space Complexity: O(n), arising from stack usage and dp.
The problem asks for the sum of the minimum values of each subarray, which is equivalent to finding the number of subarrays for which each element arr[i] is the minimum, then multiplying by arr[i], and finally summing these up.
Therefore, the focus of the problem is to find the number of subarrays for which arr[i] is the minimum. For arr[i], we find the first position left[i] to its left that is less than arr[i], and the first position right[i] to its right that is less than or equal to arr[i]. The number of subarrays for which arr[i] is the minimum is (i - left[i]) times (right[i] - i).
Note, why do we find the first position right[i] to the right that is less than or equal to arr[i], rather than less than arr[i]? This is because if we find the first position right[i] to the right that is less than arr[i], it will lead to duplicate calculations.
Let's take an example to illustrate. For the following array:
The element at index 3 is 2, the first element to its left that is less than 2 is at index 0. If we find the first element to its right that is less than 2, we get index 7. That is, the subarray interval is (0, 7). Note that this is an open interval.
0 4 3 2 5 3 2 1
* ^ *
In the same way, we can find the subarray interval for the element at index 6, and find that its subarray interval is also (0, 7). That is, the subarray intervals for the elements at index 3 and index 6 are the same. This leads to duplicate calculations.
0 4 3 2 5 3 2 1
* ^ *
If we find the first element to its right that is less than or equal to its value, there will be no duplication, because the subarray interval for the element at index 3 becomes (0, 6), and the subarray interval for the element at index 6 is (0, 7), which are not the same.
Back to this problem, we just need to traverse the array, for each element arr[i], use a monotonic stack to find the first position left[i] to its left that is less than arr[i], and the first position right[i] to its right that is less than or equal to arr[i]. The number of subarrays for which arr[i] is the minimum is (i - left[i]) times (right[i] - i), then multiply by arr[i], and finally sum these up.
Be aware of data overflow and modulo operations.
The time complexity is O(n), and the space complexity is O(n), where n is the length of the array arr.
| Approach | Complexity |
|---|---|
| Monotonic Stack Approach | Time Complexity: O(n), where n is the length of the array. |
| Dynamic Programming Approach | Time Complexity: O(n) |
| Monotonic Stack | — |
| 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. |
Leetcode 907. Sum of Subarray Minimums • Fraz • 91,137 views views
Watch 9 more video solutions →Practice Sum of Subarray Minimums with our built-in code editor and test cases.
Practice on FleetCode