Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/907.html
907. Sum of Subarray Minimums
Level
Medium
Description
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
Solution
Maintain two stacks of minimum values and the counts of minimum values, respectively. Loop over A
from left to right. Initially, each value’s count is 1. If the current value is less than the top element of the value stack, then pop the elements out of both stacks until both stacks become empty or the top element of the value stack is less than the current value. For each popped element, increase the count by the previous count. The sum is calculated as the sum of the products of all minimum values and their corresponding counts. If there are elements that are popped, then subtract the elements with their corresponding counts from the sum of products. Finally, return the sum.
-
class Solution { public int sumSubarrayMins(int[] A) { final int MODULO = 1000000007; Stack<Integer> numStack = new Stack<Integer>(); Stack<Integer> countStack = new Stack<Integer>(); int sum = 0; int product = 0; int length = A.length; for (int i = 0; i < length; i++) { int num = A[i]; int count = 1; while (!numStack.isEmpty() && numStack.peek() >= num) { int prevNum = numStack.pop(); int prevCount = countStack.pop(); count += prevCount; product -= prevNum * prevCount; } numStack.push(num); countStack.push(count); product += num * count; sum = (sum + product) % MODULO; } return sum; } }
-
// OJ: https://leetcode.com/problems/sum-of-subarray-minimums/ // Time: O(N) // Space: O(N) class Solution { public: int sumSubarrayMins(vector<int>& A) { stack<int> q; // index q.push(-1); long N = A.size(), ans = 0, sum = 0, mod = 1e9+7; for (int i = 0; i < N; ++i) { sum = (sum + A[i]) % mod; while (q.top() != -1 && A[q.top()] >= A[i]) { int j = q.top(); q.pop(); int c = j - q.top(); sum = (sum + c * (A[i] - A[j]) % mod) % mod; } q.push(i); ans = (ans + sum) % mod; } return ans; } };
-
class Solution: def sumSubarrayMins(self, arr: List[int]) -> int: n = len(arr) left = [-1] * n right = [n] * n stk = [] for i, v in enumerate(arr): while stk and arr[stk[-1]] >= v: stk.pop() if stk: left[i] = stk[-1] stk.append(i) stk = [] for i in range(n - 1, -1, -1): while stk and arr[stk[-1]] > arr[i]: stk.pop() if stk: right[i] = stk[-1] stk.append(i) mod = 10**9 + 7 return sum((i - left[i]) * (right[i] - i) * v for i, v in enumerate(arr)) % mod
-
func sumSubarrayMins(arr []int) int { mod := int(1e9) + 7 n := len(arr) left := make([]int, n) right := make([]int, n) for i := range left { left[i] = -1 right[i] = n } stk := []int{} for i, v := range arr { for len(stk) > 0 && arr[stk[len(stk)-1]] >= v { stk = stk[:len(stk)-1] } if len(stk) > 0 { left[i] = stk[len(stk)-1] } stk = append(stk, i) } stk = []int{} for i := n - 1; i >= 0; i-- { for len(stk) > 0 && arr[stk[len(stk)-1]] > arr[i] { stk = stk[:len(stk)-1] } if len(stk) > 0 { right[i] = stk[len(stk)-1] } stk = append(stk, i) } ans := 0 for i, v := range arr { ans += (i - left[i]) * (right[i] - i) * v % mod ans %= mod } return ans }
-
function sumSubarrayMins(arr: number[]): number { const n = arr.length; function getEle(i: number): number { if (i == -1 || i == n) return Number.MIN_SAFE_INTEGER; return arr[i]; } let ans = 0; const mod = 10 ** 9 + 7; let stack = []; for (let i = -1; i <= n; i++) { while (stack.length && getEle(stack[0]) > getEle(i)) { const idx = stack.shift(); ans = (ans + arr[idx] * (idx - stack[0]) * (i - idx)) % mod; } stack.unshift(i); } return ans; }