Problem statement

https://leetcode.com/problems/sum-of-subarray-minimums/

Solution

The idea is for each number with index i find how many times we meet it in total as minimum of subarray. For this we need to find:

  1. lft is the closest number to the left of i, such that it is smaller than arr[i].
  2. rgh is the closest number to the right of i, such that it is smaller or equal than arr[i].

Why we consider smaller for one side and smaller or equal for another? Because we can have equal numbers. Imagine we have ...1...1....1...1..1..., then we for each 1 we want to find subarrays where it is minimum and it is the leftest one.

  1. Finally, we evaluate (rgh[i] - i)*(i - lft[i])*arr[i] for each index, because we can go (rgh[i] - i) steps to the right and (i - lft[i]) to the left.

Complexity

It is O(n) for time and O(n) for space.

Code

class Solution:
    def sumSubarrayMins(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)