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. 1 <= A.length <= 30000
  2. 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;
}

All Problems

All Solutions