Monotonic Stack: Contribution, Span & Area

The next greater/smaller template tells you where each element's influence ends. Use it on both sides and you know the whole range where an element is the minimum (or maximum). That range answers a family of harder questions: the sum of all subarray minimums, a stock's price span, and the largest rectangle in a histogram.

The idea#

The trick is to flip the question from "for each subarray, what's its minimum?" ($O(n^2)$ subarrays) to "for each element, in how many subarrays is it the minimum?"

Say arr[i] stays the minimum for left choices of start position (itself plus the larger elements just before it) and right choices of end position. Every start can pair with every end, so arr[i] is the minimum of left * right subarrays and contributes left * arr[i] * right to the total.

• left = distance back to the previous smaller element.
• right = distance forward to the next smaller element.

Both come from one monotonic-stack pass each, so the whole sum is $O(n)$.

Duplicates: break ties on one side only#

There is one catch. If the array has equal values, a subarray like [2, 2] has two candidates for "the minimum". Using strict "smaller" on both sides counts it for both 2s; using "smaller or equal" on both sides counts it for neither. Fix it asymmetrically:

• On the left, stop at an element that is smaller or equal (<=).
• On the right, stop only at one that is strictly smaller (<).

Now each subarray belongs to exactly one of the equal minimums: the leftmost one. The rightmost 2 can't reach back past the first 2, but the first 2 can reach forward over the second.

How to spot it#

The question sums or maximizes something over every subarray or every range. Look for these signals.

• "Sum of (min / max) over all subarrays".
• "For each element, how many consecutive previous days were lower or equal?" (a span).
• "Largest rectangle" made of adjacent bars, where the shortest bar sets the height.
• A brute force that, for each element, expands left and right while the neighbors are at least as large.

Template#

Two passes find each element's reach. The left pass pops on >, so the top is the previous smaller-or-equal. The right pass pops on >=, so the top is the next strictly smaller.

stack = empty
for i from left to right:
    while stack and value at top > arr[i]: pop
    left[i] = i - top if stack else i + 1
    push i
stack = empty
for i from right to left:
    while stack and value at top >= arr[i]: pop
    right[i] = top - i if stack else n - i
    push i
total = sum of left[i] * arr[i] * right[i]

One pass: score on pop#

The two-pass version is easy to read, but you can also do it in one pass by scoring an element at the moment it's popped. Its range can't continue past the element that popped it. Keep (start, value) pairs in increasing order.

for each index i with value v:
    start = i
    while stack and value at top > v:
        pop (s, sv)
        score sv over the range s .. i - 1
        start = s                 # v fits under everything popped
    push (start, v)
for each (s, sv) left on the stack:
    score sv over the range s .. n - 1   # never blocked on the right

The key line is start = s. The new, smaller value fits under everything it popped, so it inherits the leftmost start. Entries left at the end were never blocked, so their range runs to n.

Pitfalls#

Most bugs here either change the count or lose width. Watch for these.

• Double counting equal minimums. Use <= on one side and < on the other, never the same on both.
• Default reach. If nothing blocks on the left, left = i + 1 (every start from 0); if nothing blocks on the right, right = n - i.
• Forgetting the leftovers. In the one-pass shape, entries still on the stack after the loop must be scored with a range that ends at n - 1.
• Pushing the current index instead of the inherited start. Pushing (i, v) after popping loses the range to the left.

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below.

• 901. Online Stock Span
• 907. Sum of Subarray Minimums
• 84. Largest Rectangle in Histogram
• 85. Maximal Rectangle

Hints#

Open a hint only after you have tried the problem for a while.

Key takeaways#

• Ask "in how many subarrays is this element the min?" instead of looping over subarrays.
• Contribution = left * value * right, from previous and next smaller.
• Break ties asymmetrically (<= left, < right) so equal values count once.
• Spans add up: a popped entry hands its span to the one that popped it.
• In the histogram, the popped bar is scored and the new bar inherits its start.