# Leetcode: Sum of Subarray Minimums

Sum of Subarray Minimums

Similar Problems:

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. 1 <= A.length <= 30000
2. 1 <= A[i] <= 30000

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

• Solution:
```// Blog link: https://code.dennyzhang.com/sum-of-subarray-minimums
// Basic Ideas: stack
// Element in the stack: (value, count, sum_so_far)
// Complexity: Time O(n)?, Space O(n)
import "math"
type minNode struct {
val, cnt int
sum int
}

func sumSubarrayMins(A []int) int {
res := 0
mod := int(math.Pow(10, 9)) + 7
stack := []minNode{}
for _, val := range A {
res += val
cnt := 1
for len(stack) != 0 {
node := stack[len(stack)-1]
if node.val < val {
break
}
res += val*node.cnt
cnt += node.cnt
stack = stack[0:len(stack)-1]
}
if len(stack) == 0 {
stack = append(stack, minNode{val, cnt, 0})
} else {
node := stack[len(stack)-1]
stack = append(stack, minNode{val, cnt, node.sum+node.val*node.cnt})
res += node.sum + node.val*node.cnt
}
res = res % mod
}
return res
}
```

Share It, If You Like It.