Medium

Sum of Subarray Minimums

LAB

Return the sum of the minimum value of every contiguous subarray.

EXAMPLES

Example 1

Input
{
  "arr": [
    3,
    1,
    2,
    4
  ]
}

Output
17

FUNCTION SHAPE

arr: intArray→int

SOLUTION NOTE

Contribution technique: for each A[i], count subarrays where A[i] is minimum. Use PL + NLE (or PLE + NL) to handle duplicates correctly.

Reveal reference solution +

pythonREFERENCE

def sumSubarrayMins(self, A: List[int]) -> int:
    MOD = 10 ** 9 + 7
    n = len(A)

    # Next Less or Equal on the right
    right = [n] * n
    stack = []
    for i in range(n):
        while stack and A[stack[-1]] >= A[i]:
            right[stack.pop()] = i
        stack.append(i)

    # Previous Less on the left
    left = [-1] * n
    stack = []
    for i in range(n-1, -1, -1):
        while stack and A[stack[-1]] > A[i]:
            left[stack.pop()] = i
        stack.append(i)

    res = 0
    for i in range(n):
        l, r = left[i], right[i]
        num_subarrays = (i - l) * (r - i)
        res = (res + A[i] * num_subarrays) % MOD

    return res

TimeO(n)

SpaceO(n)

Open on LeetCode ↗