LeetCode: Sum of Subarray Minimums

Posted on September 21, 2018July 26, 2020 by braindenny

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

Github: code.dennyzhang.com

Credits To: leetcode.com

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

Solution:

// https://code.dennyzhang.com/sum-of-subarray-minimums
// Basic Ideas: monotone stack
//
// Evaluate every subarray ends with A[i]
// Get the min quickly.
// Notice: we don't care about big values
//
//   3 1 2 4
//       2
//   l[i]: how many consecutive previous days whose value is bigger than this one
// Complexity: Time O(n), Space O(n)
type MyNode struct {
    value int
    count int
}

func sumSubarrayMins(A []int) int {
    stack := []MyNode{}
    res := 0
    prev := 0
    mod := int(math.Pow(10, 9)) + 7
    for _, v := range A {
        count := 1
        // elements in stack keep getting bigger
        for len(stack)>0 && stack[len(stack)-1].value >= v {
            count += stack[len(stack)-1].count
            prev -= stack[len(stack)-1].count * stack[len(stack)-1].value
            stack = stack[0:len(stack)-1]
        }
        res = (res + v*count + prev) % mod
        stack = append(stack, MyNode{v, count})
        prev = (prev + v*count) % mod
    }
    return res
}

Post Views: 0