## Algorithm

Problem Name: 907. Sum of Subarray Minimums

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 * 104`
• `1 <= arr[i] <= 3 * 104`

## Code Examples

### #1 Code Example with Java Programming

```Code - Java Programming```

``````
class Solution {

private final static int MOD = 1000_000_007;

public int sumSubarrayMins(int[] arr) {
Stack < Integer> stack = new Stack<>();
long sum = 0;
for (int i = 0; i  < = arr.length; i++) {
while (!stack.isEmpty() && (i == arr.length || arr[stack.peek()] >= arr[i])) {
int minValue = stack.pop();
int countOnLeft = stack.empty() ? -1 : stack.peek();
int countOnRight = i;
long totalCount = (minValue - countOnLeft) * (countOnRight - minValue) % MOD;
sum = (sum + (totalCount * arr[minValue])) % MOD;
}
stack.push(i);
}
return (int) (sum);
}
}
``````
Copy The Code &

Input

cmd
arr = [3,1,2,4]

Output

cmd
17

### #2 Code Example with Javascript Programming

```Code - Javascript Programming```

``````
const sumSubarrayMins = function (arr) {
const n = arr.length
const mod = 1e9 + 7, stk = []
const left = Array(n), right = Array(n)
for(let i = 0; i <  n; i++) {
left[i] = i + 1
right[i] = n - i
}
let res = 0
for(let i = 0; i  <  n; i++) {
while(stk.length && arr[stk[stk.length - 1]] > arr[i]) {
const idx = stk.pop()
right[idx] = i - idx
}
if (stk.length) left[i] = i - stk[stk.length - 1]
stk.push(i)

}
for(let i = 0; i  <  n; i++) {
res = (res + arr[i] * left[i] * right[i]) % mod
}

return res
}
``````
Copy The Code &

Input

cmd
arr = [3,1,2,4]

Output

cmd
17

### #3 Code Example with Python Programming

```Code - Python Programming```

``````
class Solution:
def sumSubarrayMins(self, A):
res, stack = 0, []
A = [float('-inf')] + A + [float('-inf')]
for i, n in enumerate(A):
while stack and A[stack[-1]] > n:
cur = stack.pop()
res += A[cur] * (i - cur) * (cur - stack[-1])
stack.append(i)
return res % (10 ** 9 + 7)
``````
Copy The Code &

Input

cmd
arr = [11,81,94,43,3]

Output

cmd
444