907. Sum of Subarray Minimums #

Problem #

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

Problem Summary #

Given an integer array 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.

Solution Ideas #

The first idea is a brute-force solution, using two nested loops to enumerate each contiguous subarray, and using one element within the interval to record the minimum value in that interval. Whenever the starting point of the interval changes, add to the final result the minimum value found from the previous interval traversal. After the entire array has been scanned once, take the final result modulo 10^9+7.
The time complexity of the brute-force solution above is especially large, because the minimum value of some interval may be the minimum value of many intervals, but we brute-force enumerate all intervals, causing the number of intervals to traverse to be especially large. The optimization point lies in how to reduce the number of intervals traversed. The second idea is to use 2 monotonic stacks. The idea we want to obtain is res = sum(A[i] * f(i)), where f(i) is the number of subarrays, and A[i] is the minimum value within this subarray. To obtain f(i), we need to find left[i] and right[i]. left[i] is the interval length to the left of A[i] that is strictly greater than A[i] (the > relation). right[i] is the interval length to the right of A[i] that is non-strictly greater (the >= relation). left[i] + 1 equals the number of subarrays ending at A[i], where A[i] is the unique minimum value; right[i] + 1 equals the number of subarrays starting at A[i], where A[i] is the first minimum value. Thus f(i) = (left[i] + 1) * (right[i] + 1). For example, for “2” in [3,1,4,2,5,3,3,1], the sequence we find is [4,2,5,3,3]. There is 1 number to the left of 2 that is greater than 2 and adjacent, and there are 3 numbers to the right of 2 that are greater than 2 and adjacent, so there are 2 * 4 = 8 sequences where 2 is the minimum value. This can also be analyzed using combinatorics: on the left of 2, we can take 0, 1, …… m numbers, for a total of (m + 1) choices; similarly, on the right, we can take 0, 1, …… n numbers, for a total of (n + 1) choices, so the total is (m + 1)(n + 1) choices. As long as f(i) is calculated, this problem becomes easy. Taking [3,1,2,4] as an example, left[i] + 1 = [1,2,1,1], right[i] + 1 = [1,3,2,1], and the corresponding product at position i is f[i] = [1 * 1, 2 * 3, 1 * 2, 1 * 1] = [1, 6, 2, 1]. The final sum of minimum values required is res = 3 * 1 + 1 * 6 + 2 * 2 + 4 * 1 = 17.
When you see a problem with this kind of mod 1e9+7, the first thing to think of is dp. The final optimized solution uses DP + a monotonic stack. The monotonic stack maintains a sequence of corresponding indices whose values in the array are gradually increasing. Define dp[i + 1] to represent the sum of the minimum values of subarrays ending at A[i]. The state transition equation is dp[i + 1] = dp[prev + 1] + (i - prev) * A[i], where prev is the previous number smaller than A[i]. Since we maintain a monotonic stack, prev is the stack top element. (i - prev) * A[i] means that before prev appears, A[i] is the minimum in these intervals, and there are i - prev such intervals, so the sum of minimum values should be (i - prev) * A[i]. Adding dp[prev + 1] gives the sum of minimum values for dp[i + 1]. Taking [3, 1, 2, 4, 3] as an example, when i = 4, all subarrays ending at A[4] are:
```
  [3]  
  [4, 3]  
  [2, 4, 3]  
  [1, 2, 4, 3]  
  [3, 1, 2, 4, 3] 
```
In this case, stack.peek() = 2, A[2] = 2. For the first two subarrays [3] and [4, 3], the sum of minimum values = (i - stack.peek()) * A[i] = 6. The last 3 subarrays are [2, 4, 3], [1, 2, 4, 3], and [3, 1, 2, 4, 3]. They all contain 2, and 2 is the previous number smaller than 3, so dp[i + 1] = dp[stack.peek() + 1] = dp[2 + 1] = dp[3] = dp[2 + 1]. That is, we need to find the value of dp[i + 1] when i = 2. Continuing the recurrence, the previous value smaller than 2 is 1, A[1] = 1. dp[3] = dp[1 + 1] + (2 - 1) * A[2]= dp[2] + 2. dp[2] = dp[1 + 1]. When i = 1, prev = -1, meaning no one is smaller than A[1], so dp[2] = dp[1 + 1] = dp[-1 + 1] + (1 - (-1)) * A[1] = 0 + 2 * 1 = 2. Iterating back, dp[3] = dp[2] + 2 = 2 + 2 = 4. dp[stack.peek() + 1] = dp[2 + 1] = dp[3] = 4. So dp[i + 1] = 4 + 6 = 10.
Problems with solution ideas similar to this problem include problem 828 and problem 891.

Code #


package leetcode

// Solution 1: The fastest solution is DP + monotonic stack
func sumSubarrayMins(A []int) int {
	stack, dp, res, mod := []int{}, make([]int, len(A)+1), 0, 1000000007
	stack = append(stack, -1)

	for i := 0; i < len(A); i++ {
		for stack[len(stack)-1] != -1 && A[i] <= A[stack[len(stack)-1]] {
			stack = stack[:len(stack)-1]
		}
		dp[i+1] = (dp[stack[len(stack)-1]+1] + (i-stack[len(stack)-1])*A[i]) % mod
		stack = append(stack, i)
		res += dp[i+1]
		res %= mod
	}
	return res
}

type pair struct {
	val   int
	count int
}

// Solution 2: Use two monotonic stacks
func sumSubarrayMins1(A []int) int {
	res, n, mod := 0, len(A), 1000000007
	lefts, rights, leftStack, rightStack := make([]int, n), make([]int, n), []*pair{}, []*pair{}
	for i := 0; i < n; i++ {
		count := 1
		for len(leftStack) != 0 && leftStack[len(leftStack)-1].val > A[i] {
			count += leftStack[len(leftStack)-1].count
			leftStack = leftStack[:len(leftStack)-1]
		}
		leftStack = append(leftStack, &pair{val: A[i], count: count})
		lefts[i] = count
	}

	for i := n - 1; i >= 0; i-- {
		count := 1
		for len(rightStack) != 0 && rightStack[len(rightStack)-1].val >= A[i] {
			count += rightStack[len(rightStack)-1].count
			rightStack = rightStack[:len(rightStack)-1]
		}
		rightStack = append(rightStack, &pair{val: A[i], count: count})
		rights[i] = count
	}

	for i := 0; i < n; i++ {
		res = (res + A[i]*lefts[i]*rights[i]) % mod
	}
	return res
}

// Solution 3: Brute-force solution, with many repeated checks of subarrays
func sumSubarrayMins2(A []int) int {
	res, mod := 0, 1000000007
	for i := 0; i < len(A); i++ {
		stack := []int{}
		stack = append(stack, A[i])
		for j := i; j < len(A); j++ {
			if stack[len(stack)-1] >= A[j] {
				stack = stack[:len(stack)-1]
				stack = append(stack, A[j])
			}
			res += stack[len(stack)-1]
		}
	}
	return res % mod
}