077. Sum of Subarray Minimums

Why this mechanism works

Count how many subarrays choose each position as their minimum. Duplicate minima require a unique owner: choose the rightmost equal minimum. Find the previous strictly smaller position and the next smaller-or-equal position. Their distances give independent choices for the subarray's left and right boundaries.

State and boundaries

previous[i] is the nearest strictly smaller index to the left; following[i] is the nearest <= index to the right.

Protocol

1. Scan left to right, popping >= values to find previous strict blockers.
2. Scan right to left, popping > values to find following non-strict blockers.
3. Add nums[i]*(i-previous[i])*(following[i]-i) for every i.

Visualization

[2,2] -> rightmost minimum owns [0,2)
index 0 owns [0,1)
index 1 owns [1,2) and [0,2)
sum=2+2+2=6

Python implementation

def sum_subarray_minimums(nums):
    n = len(nums)
    previous, following = [-1] * n, [n] * n
    stack = []
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        previous[i] = stack[-1] if stack else -1
        stack.append(i)
    stack = []
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] > nums[i]:
            stack.pop()
        following[i] = stack[-1] if stack else n
        stack.append(i)
    return sum(value * (i - previous[i]) * (following[i] - i)
               for i, value in enumerate(nums))

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L2 sum_subarray_minimums: n = len(nums)
nums=[3, 1, 2, 4]; n=4

L3 sum_subarray_minimums: previous, following = [-1] * n, [n] * n
nums=[3, 1, 2, 4]; n=4; following=[4, 4, 4, 4]; previous=[-1, -1, -1, -1]

L4 sum_subarray_minimums: stack = []
nums=[3, 1, 2, 4]; n=4; following=[4, 4, 4, 4]; previous=[-1, -1, -1, -1]; stack=[]

L5 sum_subarray_minimums: for i in range(n):
nums=[3, 1, 2, 4]; n=4; following=[4, 4, 4, 4]; previous=[-1, -1, -1, -1]; stack=[]; i=0

L9 sum_subarray_minimums: stack.append(i)
nums=[3, 1, 2, 4]; n=4; following=[4, 4, 4, 4]; previous=[-1, -1, -1, -1]; stack=[0]; i=0

L5 sum_subarray_minimums: for i in range(n):
nums=[3, 1, 2, 4]; n=4; following=[4, 4, 4, 4]; previous=[-1, -1, -1, -1]; stack=[0]; i=1

L7 sum_subarray_minimums: stack.pop()
nums=[3, 1, 2, 4]; n=4; following=[4, 4, 4, 4]; previous=[-1, -1, -1, -1]; stack=[]; i=1

L9 sum_subarray_minimums: stack.append(i)
nums=[3, 1, 2, 4]; n=4; following=[4, 4, 4, 4]; previous=[-1, -1, -1, -1]; stack=[1]; i=1

... 19 intermediate state changes omitted ...

L17 <genexpr>: for i, value in enumerate(nums))
.0=enumerate; following=[1, 4, 4, 4]; previous=[-1, -1, 1, 2]; i=1; value=1

L17 <genexpr>: for i, value in enumerate(nums))
.0=enumerate; following=[1, 4, 4, 4]; previous=[-1, -1, 1, 2]; i=2; value=2

L17 <genexpr>: for i, value in enumerate(nums))
.0=enumerate; following=[1, 4, 4, 4]; previous=[-1, -1, 1, 2]; i=3; value=4

L17 <genexpr>: for i, value in enumerate(nums))
.0=enumerate; following=[1, 4, 4, 4]; previous=[-1, -1, 1, 2]; i=3; value=4

L2 sum_subarray_minimums: n = len(nums)
nums=[2, 2]; n=2

L3 sum_subarray_minimums: previous, following = [-1] * n, [n] * n
nums=[2, 2]; n=2; following=[2, 2]; previous=[-1, -1]

L4 sum_subarray_minimums: stack = []
nums=[2, 2]; n=2; following=[2, 2]; previous=[-1, -1]; stack=[]

L5 sum_subarray_minimums: for i in range(n):
nums=[2, 2]; n=2; following=[2, 2]; previous=[-1, -1]; stack=[]; i=0

L9 sum_subarray_minimums: stack.append(i)
nums=[2, 2]; n=2; following=[2, 2]; previous=[-1, -1]; stack=[0]; i=0

L5 sum_subarray_minimums: for i in range(n):
nums=[2, 2]; n=2; following=[2, 2]; previous=[-1, -1]; stack=[0]; i=1

L7 sum_subarray_minimums: stack.pop()
nums=[2, 2]; n=2; following=[2, 2]; previous=[-1, -1]; stack=[]; i=1

L9 sum_subarray_minimums: stack.append(i)
nums=[2, 2]; n=2; following=[2, 2]; previous=[-1, -1]; stack=[1]; i=1

... 5 intermediate state changes omitted ...

L16 <genexpr>: return sum(value * (i - previous[i]) * (following[i] - i)
.0=enumerate; following=[1, 2]; previous=[-1, -1]

L17 <genexpr>: for i, value in enumerate(nums))
.0=enumerate; following=[1, 2]; previous=[-1, -1]; i=0; value=2

L17 <genexpr>: for i, value in enumerate(nums))
.0=enumerate; following=[1, 2]; previous=[-1, -1]; i=1; value=2

L17 <genexpr>: for i, value in enumerate(nums))
.0=enumerate; following=[1, 2]; previous=[-1, -1]; i=1; value=2

Why the solution is correct

Between these blockers, every value is at least nums[i], and no equal minimum to its right is included. Thus i owns exactly the subarrays choosing a left boundary after previous[i] and an end before following[i]. Every subarray has one rightmost minimum, so contributions partition the set without duplication.

Time and space

O(n) time and O(n) space. Integer multiplication costs depend on magnitude beyond the unit-cost model.

Common mistakes

Using strict comparisons on both sides double-counts tied minima; using non-strict comparisons on both can miss them. Tie ownership is part of the proof.

Reasoning card

Transfer exercise

Subtract summed minima from summed maxima to obtain the sum of all subarray ranges.