Monotonic Stack Explained: Next Greater Element and More

A monotonic stack is a stack whose items are always in sorted order (all increasing or all decreasing from bottom to top). Before pushing a new item, you pop everything that would break the order, and those pops are where the answers come from.

It solves "for each item, find the nearest item to the left or right that is bigger (or smaller)" in O(n) instead of O(n²).

Next greater element#

For each number, find the first larger number to its right, or -1.

Keep a stack of indexes still waiting for their answer, with values decreasing from bottom to top. When a bigger number arrives, it is the answer for every smaller waiting number, so pop them and record it:

def next_greater(nums):
    result = [-1] * len(nums)
    waiting = []                         # indexes, values decreasing
    for i, x in enumerate(nums):
        while waiting and nums[waiting[-1]] < x:
            result[waiting.pop()] = x
        waiting.append(i)
    return result

print(next_greater([2, 1, 2, 4, 3]))
print(next_greater([5, 4, 3, 2, 1]))

[4, 2, 4, -1, -1]
[-1, -1, -1, -1, -1]

Each index is pushed once and popped at most once, so the whole thing is O(n) even with the inner while.

Daily temperatures#

For each day, how many days until a warmer one? 0 if none. The same pattern, but record the distance instead of the value:

def days_until_warmer(temps):
    result = [0] * len(temps)
    waiting = []
    for i, t in enumerate(temps):
        while waiting and temps[waiting[-1]] < t:
            j = waiting.pop()
            result[j] = i - j
        waiting.append(i)
    return result

print(days_until_warmer([73, 74, 75, 71, 69, 72, 76, 73]))

[1, 1, 4, 2, 1, 1, 0, 0]

Stock span#

The span of a day's price is how many consecutive days, ending today, had a price less than or equal to today's. Look left: keep a stack of earlier days with higher prices; pop the ones today's price beats.

def stock_span(prices):
    spans, stack = [], []                # stack holds indexes, prices decreasing
    for i, p in enumerate(prices):
        while stack and prices[stack[-1]] <= p:
            stack.pop()
        spans.append(i + 1 if not stack else i - stack[-1])
        stack.append(i)
    return spans

print(stock_span([100, 80, 60, 70, 60, 75, 85]))

[1, 1, 1, 2, 1, 4, 6]

On the day the price is 75, the three days before it (60, 70 and 60) were all lower, but the day before those was 80, which is higher, so the span stops there: 3 earlier days plus today gives a span of 4.

Largest rectangle in a histogram#

Bars of width 1 have heights h. Find the largest rectangle that fits under them.

For each bar, the widest rectangle of that bar's height stretches until a shorter bar on each side. An increasing stack finds both borders: when a shorter bar arrives, every taller bar on the stack has just found its right border, and its left border is the bar below it on the stack.

def largest_rectangle(heights):
    stack, best = [], 0                  # indexes, heights increasing
    for i, h in enumerate(heights + [0]):   # the 0 flushes the stack at the end
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

print(largest_rectangle([2, 1, 5, 6, 2, 3]))
print(largest_rectangle([2, 4]))

10
4

The answer 10 comes from the bars of height 5 and 6: height 5 × width 2.

Which direction and which order?#

Common mistakes#

Practice#

def next_smaller(nums):
    result = [-1] * len(nums)
    waiting = []
    for i, x in enumerate(nums):
        while waiting and nums[waiting[-1]] > x:
            result[waiting.pop()] = x
        waiting.append(i)
    return result

print(next_smaller([4, 8, 5, 2, 25]))
print(next_smaller([1, 2, 3]))

[2, 5, 2, -1, -1]
[-1, -1, -1]

Key takeaway#

Next: halving the search space, in Binary Search.