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
}
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.