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 modulo109 + 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 * 104
1 <= arr[i] <= 3 * 104
Intuition
Approach:
Brute:
In N^2 generate all sub-arrays , Then Take one more N to find min in arrays
N^3
Optimal
Use stack
Basically find the ith element is min till what range in left and right
Let
arr = 3 1 2 4
lef = 1 2 1 1
rig = 1 3 2 1
Now, arr*left*right is answer
Links
Video Links
Approach 1:
C++
class Solution {
public:
int sumSubarrayMins(vector<int>& arr) {
int n= arr.size();
vector<int> left(n),right(n);
stack<pair<int,int>>s,s2;
for(int i=0;i<n;i++){
int count=1;
while(!s.empty() and s.top().first > arr[i]){
count+=s.top().second;
s.pop();
}
s.push({arr[i],count});
left[i]=count;
}
for(int i=n-1;i>=0;i--){
int count=1;
while(!s2.empty() and s2.top().first >= arr[i]){
count+=s2.top().second;
s2.pop();
}
s2.push({arr[i],count});
right[i]=count;
}
long long int sum=0,mod=1e9+7;
for (int i = 0; i < n; i++){
sum=(sum+(long long int)arr[i]*left[i]*right[i])%mod;
}
return sum;
}
};