# Solution For Sum Of Subarray Minimums

Problem:

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 10^9 + 7.

Solution:

This problem can be solved using a stack-based algorithm that calculates the answer by computing the contribution of each element to the final answer. We use two stacks:

1. stack V: stores the unique values in the array arr.
2. stack W: stores the sum of the subarrays that end at or before each element in V.

The idea is to iterate over the array arr and calculate the sum of the subarray minimums for each element in arr. To do that, we take the following steps:

1. Pop the top element v of stack V and w of stack W if the current element in arr is smaller than v.
2. Let the current element in arr be a[i]. While the value v at the top of stack V is greater than a[i], pop it and add the corresponding sum w to the final answer. The subarrays that end at or before v also end at or before a[i], so we add w × (i – index_v) to the sum of min(b), where index_v is the index of v in arr.
3. Push a[i] to stack V and calculate the sum of the subarrays that end at or before a[i] by adding the sum of the subarrays that ended at or before the previous element in arr to a[i] × (i – index), where index is the index of the previous element in arr. Push the sum to stack W.

After iterating over all the elements in arr, the final answer is the sum of the values in stack W mod 10^9 + 7.

Pseudo code:

stack V, stack W
for i in range(N):
while V and arr[i] < V[-1]:
V.pop()
W.pop()
if not V:
index = -1
else:
index = V[-1] s = (i – index) * arr[i] V.append(arr[i])
W.append((W[-1] if W else 0) + s)
return sum(W) % (10 ** 9 + 7)

Time Complexity:

The time complexity of this solution is O(N), where N is the length of the input array arr, because we visit each element in arr exactly once and perform constant time operations for each element.

Space Complexity:

The space complexity of this solution is O(N), because we store each element in arr in stack V and we also store the sum of the subarrays that end at or before each element in arr in stack W.

## Step by Step Implementation For Sum Of Subarray Minimums

```class Solution {
public int sumSubarrayMins(int[] A) {
// initialize prefix and suffix arrays
int[] prefix = new int[A.length];
int[] suffix = new int[A.length];

// initialize current minimum to the first element in the array
int currMin = A[0];

// fill prefix array
for (int i = 0; i < A.length; i++) {
// update current minimum
currMin = Math.min(currMin, A[i]);

// update prefix array at index i
prefix[i] = currMin;
}

// reset current minimum
currMin = A[A.length - 1];

// fill suffix array in reverse
for (int i = A.length - 1; i >= 0; i--) {
// update current minimum
currMin = Math.min(currMin, A[i]);

// update suffix array at index i
suffix[i] = currMin;
}

// initialize sum
int sum = 0;

// calculate sum of subarray minimums
for (int i = 0; i < A.length; i++) {
sum += Math.min(prefix[i], suffix[i]);
}

return sum;
}
}```
```Given an array of integers A, find the sum of min(B), where B ranges over every (contiguous) subarray of A.

Since the answer may be large, return the answer modulo 10^9 + 7.

Example 1:

Input: [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.

Note:

1 <= A.length <= 30000
1 <= A[i] <= 30000```
```var sumOfSubarrayMins = function(A) {
let totalSum = 0;

for(let i = 0; i < A.length; i++){
let min = A[i];

for(let j = i; j < A.length; j++){
min = Math.min(min, A[j]);
totalSum += min;
}
}

};```
```class Solution {
public:
int sumSubarrayMins(vector& A) {
int MOD = 1e9+7;
int n = A.size();
stack s;
vector left(n);
for (int i = 0; i < n; ++i) {
int count = 1;
while (!s.empty() && s.top() > A[i]) {
count += left[s.top()];
s.pop();
}
left[i] = count;
s.push(i);
}
while (!s.empty()) s.pop();
vector right(n);
for (int i = n-1; i >= 0; --i) {
int count = 1;
while (!s.empty() && s.top() >= A[i]) {
count += right[s.top()];
s.pop();
}
right[i] = count;
s.push(i);
}
int ans = 0;
for (int i = 0; i < n; ++i) {
ans += A[i] * left[i] * right[i];
ans %= MOD;
}
return ans;
}
};```
```class Solution {
public int SumSubarrayMins(int[] A) {

// create a stack to keep track of the indices of the array
Stack stack = new Stack();

// create an array to store the results
int[] result = new int[A.Length];

// iterate through the array
for(int i = 0; i < A.Length; i++){

// while the stack is not empty and the current element is less than the element at the top of the stack
while(stack.Count != 0 && A[i] < A[stack.Peek()]){

// pop the element off the top of the stack
int index = stack.Pop();

// calculate the number of subarrays that have the element at the current index as the minimum
int numSubarrays = i - index;

// if the stack is empty, then all subarrays from the current index to the end of the array have the current element as the minimum
if(stack.Count == 0)
numSubarrays = i + 1;
// otherwise, the number of subarrays is the difference between the current index and the index of the element at the top of the stack
else
numSubarrays = i - stack.Peek() - 1;

// calculate the sum of subarray minimums and store it in the result array
result[index] += A[index] * numSubarrays;
}

// push the current index onto the stack
stack.Push(i);
}

// while the stack is not empty
while(stack.Count != 0){

// pop the element off the top of the stack
int index = stack.Pop();

// calculate the number of subarrays that have the element at the current index as the minimum
int numSubarrays = A.Length - index;

// if the stack is empty, then all subarrays from the current index to the end of the array have the current element as the minimum
if(stack.Count == 0)
numSubarrays = A.Length - index;
// otherwise, the number of subarrays is the difference between the current index and the index of the element at the top of the stack
else
numSubarrays = A.Length - stack.Peek() - 1;

// calculate the sum of subarray minimums and store it in the result array
result[index] += A[index] * numSubarrays;
}

// return the sum of the result array
return result.Sum();
}
}```

Scroll to Top
[gravityforms id="5" description="false" titla="false" ajax="true"]