Problem URL: Sum of subarray minimums

We can solve it by using stack. We can iterate over the array, and for each element, we can check if the stack is empty or the top of the stack is greater than the current element. If the stack is empty or the top of the stack is greater than the current element, we can push the index of the current element to the stack. If the stack is not empty and the top of the stack is less than the current element, we can pop the top of the stack. We can calculate the sum of the subarray minimums by using the formula sum += (i - stack[-1]) * (stack[-1] - stack[-2]) * A[stack[-1]]. We can return the sum of the subarray minimums.

class Solution:
    def sumSubarrayMins(self, arr: List[int]) -> int:
        MOD, stack = 10**9+7, []
        res = 0
        for i in range(len(arr)):
            while stack and arr[i] <= arr[stack[-1]]:
                _id = stack.pop()
                l = stack[-1] if stack else -1
                r = i
                res += (r-_id) * (_id-l) * arr[_id]
                res %= MOD
            stack.append(i)

        while stack:
            _id = stack.pop()
            l = stack[-1] if stack else -1
            r = len(arr)
            res += (r-_id) * (_id-l) * arr[_id]
            res %= MOD

        return res

Time complexity: O(n), n is the length of arr
Space complexity: O(n)