Sum of Subarray Minimums — Monotonic Stack Contribution

Problem

Find the sum of min(subarray) for all subarrays.

Approach — Contribution Technique

For each element arr[i], find:

left[i] = distance to previous smaller element (or start)
right[i] = distance to next smaller/equal element (or end)
Contribution = arr[i] * left[i] * right[i]

Use monotonic stack twice (or once) to compute these.

Time: O(n) | Space: O(n)

Solutions

Python

class Solution:
    def sumSubarrayMins(self, arr: list[int]) -> int:
        MOD=10**9+7; n=len(arr)
        left=[0]*n; right=[0]*n; stack=[]
        for i in range(n):
            while stack and arr[stack[-1]]>=arr[i]: stack.pop()
            left[i]=i+1 if not stack else i-stack[-1]
            stack.append(i)
        stack=[]
        for i in range(n-1,-1,-1):
            while stack and arr[stack[-1]]>arr[i]: stack.pop()
            right[i]=n-i if not stack else stack[-1]-i
            stack.append(i)
        return sum(arr[i]*left[i]*right[i] for i in range(n))%MOD

Complexity

Time: O(n) | Space: O(n)