Problem statement

https://binarysearch.com/problems/Every-Sublist-Min-Sum/

Solution

Equal to Leetcode 0907 Sum of Subarray Minimums.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, arr):
        n = len(arr)
        rgh, lft = [n]*n, [-1]*n

        stack1 = []
        for i in range(n):
            while stack1 and arr[i] < arr[stack1[-1]]: 
                idx = stack1.pop()
                rgh[idx] = i
            stack1.append(i)
            
        stack2 = []
        for i in range(n-1, -1, -1):
            while stack2 and arr[i] <= arr[stack2[-1]]:
                idx = stack2.pop()
                lft[idx] = i
            stack2.append(i)
            
        return sum((rgh[i] - i)*(i - lft[i])*arr[i] for i in range(n)) % (10**9 + 7)