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 * 104The key challenge in #907 Sum of Subarray Minimums is efficiently computing the minimum value for every possible subarray. A brute-force approach would check all subarrays and track their minimums, but this leads to O(n^2) or worse time complexity, which is too slow for large inputs.
An optimized strategy uses a monotonic increasing stack. The main idea is to determine how many subarrays consider a particular element as their minimum. For each element, we calculate the distance to the previous smaller element and the next smaller element. These distances represent how far the element can extend left and right while still being the smallest value.
By multiplying these spans, we can compute the number of subarrays where the element is the minimum and add its contribution to the final sum. The stack helps maintain order and quickly identify boundaries. This approach processes each element a constant number of times, resulting in an efficient solution.
Time Complexity: O(n) using a monotonic stack.
Space Complexity: O(n) for stack storage and auxiliary arrays.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Monotonic Stack with Contribution Counting | O(n) | O(n) |
take U forward
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.
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.
1const sumSubarrayMins = (arr) => {
2 const MOD = 1e9 + 7;
3 const n = arr.length;
4
The JavaScript solution applies similar logic, effectively utilizing an array to serve as a stack, ensuring sequential calculation of array elements’ subarray contributions.
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.
Time Complexity: O(n)
Space Complexity: O(n), arising from stack usage and dp.
1#include <stack>
using namespace std;
typedef long long ll;
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int MOD = 1e9 + 7;
int n = arr.size();
vector<int> dp(n);
stack<int> s;
ll result = 0;
for (int i = 0; i < n; ++i) {
while (!s.empty() && arr[s.top()] >= arr[i]) s.pop();
int k = (s.empty()) ? i + 1 : i - s.top();
dp[i] = (arr[i] * k + (s.empty() ? 0 : dp[s.top()])) % MOD;
result = (result + dp[i]) % MOD;
s.push(i);
}
return (int)result;
}
};Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, this problem or its variations frequently appear in technical interviews at top companies. It tests knowledge of monotonic stacks, array processing, and contribution-based counting techniques, which are common interview patterns.
A monotonic stack is the most effective data structure for this problem. It helps maintain elements in increasing order and allows efficient computation of previous and next smaller elements for each index.
The optimal approach uses a monotonic increasing stack to determine how far each element can extend as the minimum in subarrays. By finding the previous and next smaller elements, we can calculate how many subarrays each value contributes to. This reduces the complexity to O(n).
Previous and next smaller elements define the boundaries where a value stops being the minimum in a subarray. Using these boundaries, we can calculate the total number of subarrays in which the element acts as the minimum and add its contribution to the sum.
In this C++ solution, a stack maintains previously seen elements, easing computation of minimum contributions by referring to the dp derived from prior computed sections.