Monotonic Stacks

A monotonic stack is an ordinary stack that you keep either strictly increasing or strictly decreasing from bottom to top, by popping off any elements that would break that order before pushing a new one on. It sounds like a small bookkeeping trick, but it quietly turns an entire family of “find the next bigger/smaller thing” problems from an O(n^2) nested loop into a single O(n) pass. If you’ve ever needed the next warmer day, the next taller building, or the largest rectangle that fits under a skyline, you were looking for a monotonic stack.

Overview / How it works

Picture the Next Greater Element problem: for every number in a list, find the first number to its right that is bigger. The brute-force approach scans forward from every index, which is O(n) work repeated n times, giving O(n^2). A monotonic stack solves it in one left-to-right pass.

Think of the stack as a waiting line of indices that haven’t found their “next greater” value yet. As you scan left to right, before you push the current index you first ask: does the current value beat the value at the top of the stack? If yes, that top index’s wait is over — pop it and record the current value as its answer. Keep popping while the current value keeps beating the new top. Once the current value no longer beats the top (or the stack is empty), push the current index; it now joins the line, waiting for its own next greater value. Because you only ever pop when the current value is strictly bigger than the value below it, the values still sitting on the stack always form a decreasing sequence from bottom to top — that’s the “monotonic” part.

The mirror-image version, an increasing stack that pops whenever the current value is smaller than the top, finds the next smaller element instead. Whichever direction you need, the shape of the algorithm is identical: scan once, pop while the ordering is violated, push, repeat.

Why is this O(n) and not O(n^2), even though there’s a while loop nested inside a for loop? Because every index is pushed onto the stack exactly once and popped at most once, over the entire run of the algorithm — not per outer iteration. Summed across the whole scan, the total number of pushes and pops is at most 2n. This is called amortized analysis: one particular iteration’s while loop might pop many items, but the total work across all iterations is still bounded by n.

Time and Space Complexity

Here n is the number of elements in the input list.

Pattern	Time	Space	Why
Single monotonic-stack pass (Next Greater/Smaller Element, Daily Temperatures)	O(n)	O(n)	Each index is pushed once and popped at most once, so total stack operations across the whole loop are bounded by 2n, even though a single iteration’s while loop can pop several items at once.
Largest Rectangle in Histogram	O(n)	O(n)	Same push-once/pop-once argument applied to a stack of bar indices; a sentinel value appended at the end guarantees every remaining bar gets popped and priced.
Brute-force alternative (nested loop, no stack)	O(n^2)	O(1) extra	For every element, scanning everything to its right to find the next greater/smaller value is O(n) work, repeated for all n starting points.

Examples

Example 1: Next Greater Element

For each number, find the first number to its right that is strictly greater; use -1 if none exists.

def next_greater_elements(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []  # indices of elements waiting for a greater value, in decreasing order

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:
            top = stack.pop()
            result[top] = num
        stack.append(i)

    return result


nums = [4, 5, 2, 10, 8]
print(next_greater_elements(nums))

Output:

[5, 10, 10, -1, -1]

Tracing it: 4 is immediately beaten by 5. 5 waits until 10 shows up. 2 also gets resolved by 10 since it was still sitting on the stack underneath 5 when 10 arrived. Nothing ever beats 10 or 8, so they stay -1.

Example 2: Daily Temperatures

Given a list of daily temperatures, find how many days you’d have to wait for a warmer day. This is the same pattern as Example 1, except the stack holds indices (so we can compute a distance) and we record i - previous_day instead of the value itself.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack: list[int] = []  # indices of days waiting for a warmer day

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            previous_day = stack.pop()
            answer[previous_day] = i - previous_day
        stack.append(i)

    return answer


temperatures = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temperatures))

Output:

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

Day 2 (75°) has to wait until day 6 (76°), four days later, because 71°, 69°, and 72° along the way never beat 75°. The last two days never see a warmer day within the list, so they default to 0.

Example 3: Largest Rectangle in Histogram

Given bar heights of a histogram (each bar has width 1), find the area of the largest rectangle that fits entirely under the skyline. This is the classic “realistic” monotonic stack problem: instead of resolving a value, each pop computes an area using the popped bar’s height and a width measured from the stack.

def largest_rectangle_area(heights: list[int]) -> int:
    stack: list[int] = []  # indices of bars kept in increasing height order
    max_area = 0
    extended_heights = heights + [0]  # sentinel forces the stack to empty out at the end

    for i, height in enumerate(extended_heights):
        while stack and extended_heights[stack[-1]] >= height:
            top = stack.pop()
            bar_height = extended_heights[top]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, bar_height * width)
        stack.append(i)

    return max_area


heights = [2, 1, 5, 6, 2, 3]
print(largest_rectangle_area(heights))

Output:

10

The winning rectangle uses the bars of height 5 and 6 (indices 2 and 3): once the algorithm reaches the bar of height 2 at index 4, it pops the height-6 bar (area 6 × 1 = 6) and then the height-5 bar, whose width now stretches from index 2 up to (but not including) the last remaining stack index, giving 5 × 2 = 10 — the maximum found.

How it works step by step

Let’s trace next_greater_elements on nums = [3, 1, 4, 2] one index at a time.

i	nums[i]	Stack before (indices : values)	What happens	Stack after
0	3	[] : []	Stack is empty, nothing to pop. Push index 0.	[0] : [3]
1	1	[0] : [3]	nums[0] = 3 is not less than 1, so no pop. Push index 1.	[0, 1] : [3, 1]
2	4	[0, 1] : [3, 1]	nums[1] = 1 < 4 → pop, result[1] = 4. Then nums[0] = 3 < 4 → pop, result[0] = 4. Stack now empty. Push index 2.	[2] : [4]
3	2	[2] : [4]	nums[2] = 4 is not less than 2, so no pop. Push index 3.	[2, 3] : [4, 2]

After the loop ends, indices 2 and 3 are still sitting on the stack — nothing greater ever showed up for them, so they keep their default value of -1. The final result is [4, 4, -1, -1].

Common Mistakes

Mistake 1: Storing values instead of indices

If the answer you need depends on position — like how many days until a warmer day — storing raw values on the stack throws away the information you need to compute that distance.

def days_until_warmer_wrong(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack = []  # BUG: storing temperature values instead of indices

    for i, temp in enumerate(temperatures):
        while stack and stack[-1] < temp:
            warmer_temp = stack.pop()
            answer[warmer_temp] = 1  # BUG: using a temperature as a list index
        stack.append(temp)

    return answer


print(days_until_warmer_wrong([73, 74, 75]))

Output:

IndexError: list assignment index out of range

This crashes immediately: answer only has 3 slots (indices 0-2), but warmer_temp is a temperature like 73, which is nowhere near a valid index. The fix is to push and pop i (the index), and look the temperature up with temperatures[stack[-1]] whenever you need the value:

def days_until_warmer_correct(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack: list[int] = []  # stores indices, not temperatures

    for i, temp in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < temp:
            previous_day = stack.pop()
            answer[previous_day] = i - previous_day
        stack.append(i)

    return answer


print(days_until_warmer_correct([73, 74, 75]))

Output:

[1, 1, 0]

Mistake 2: Using the wrong comparison operator with duplicate values

Whether you use < or <= (or > vs >=) in the popping condition decides how ties are handled, and it’s the single most common source of monotonic-stack bugs.

def next_greater_wrong(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] <= num:  # BUG: <= treats equal values as "greater"
            top = stack.pop()
            result[top] = num
        stack.append(i)

    return result


print(next_greater_wrong([1, 3, 3, 2]))

Output:

[3, 3, -1, -1]

The element 3 at index 1 gets marked as having a next greater element of 3 — but 3 is not greater than 3, it’s equal. The <= condition incorrectly pops an equal value as if it had found something bigger. Using a strict < fixes it:

def next_greater_correct(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []

    for i, num in enumerate(nums):
        while stack and nums[stack[-1]] < num:  # strict: equal values are not "greater"
            top = stack.pop()
            result[top] = num
        stack.append(i)

    return result


print(next_greater_correct([1, 3, 3, 2]))

Output:

[3, -1, -1, -1]

Now the second 3 correctly stays unresolved, since nothing strictly bigger ever follows it.

Best Practices

• Reach for a monotonic stack whenever a problem asks for “next/previous greater or smaller element”, spans, or areas under a skyline-like shape — it replaces an O(n^2) brute force with O(n).
• Store indices on the stack, not values, so you can compute distances (i - stack[-1]) and still look the value up with nums[stack[-1]] whenever you need it.
• Decide up front whether you need strictly greater/smaller or greater-or-equal/smaller-or-equal, and pick <, <=, >, or >= to match — that choice is what determines how ties are resolved.
• Use a plain Python list as the stack: append() and argument-less pop() operate on the end of the list in O(1) amortized time. Never call pop(0) or insert(0, ...) on a list-based stack — those are O(n) and defeat the whole point.
• When every remaining stack entry needs resolving at the end (as in Largest Rectangle in Histogram), append a sentinel value (like 0) so the main loop flushes the stack for you instead of writing a second cleanup loop.
• Trace a small 4-6 element example by hand before trusting your implementation — monotonic stack bugs are almost always an off-by-one width calculation or a wrong comparison operator, and both only surface on specific inputs (especially ones with duplicates).

Practice Exercises

Exercise 1: Next Smaller Element

Write next_smaller_elements(nums: list[int]) -> list[int] that returns, for each index, the value of the next element to its right that is strictly smaller, or -1 if none exists. Hint: use an increasing monotonic stack (pop while the top’s value is greater than the current value). Test it on [4, 8, 5, 2, 25]; the expected output is [2, 5, 2, -1, -1].

Exercise 2: Stock Span Problem

On day i, the stock span is the number of consecutive days ending at day i (including day i) during which the price never exceeded today’s price. Write calculate_span(prices: list[int]) -> list[int] using a monotonic stack of indices, kept in decreasing order of price, so you never have to rescan previous days. Test it on prices = [100, 80, 60, 70, 60, 75, 85]. Expected output: [1, 1, 1, 2, 1, 4, 6].

Exercise 3: Trapping Rain Water

Given a list of non-negative integers representing an elevation map (each bar has width 1), compute how much rainwater it can trap after raining. For example, heights = [0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1] traps 6 units total. This is solvable with a monotonic stack that tracks decreasing bar heights and, whenever a taller bar arrives, pops the stack and computes the water trapped between the popped bar and the new taller bar (similar in spirit to Example 3’s area calculation, but computing trapped water instead of rectangle area).

Summary

• A monotonic stack keeps its elements strictly increasing or strictly decreasing by popping violators before every push, turning many “next/previous greater or smaller” problems into O(n) instead of O(n^2).
• Store indices, not values, whenever the answer needs a position, a distance, or the value that got popped.
• Use a decreasing stack to find the next greater element, and an increasing stack to find the next smaller element.
• Every element is pushed once and popped at most once, so total work across the whole scan is O(n) time; the stack itself can grow to O(n) space in the worst case (e.g. an already-sorted input that never triggers a pop).
• The comparison operator (< vs <=, > vs >=) decides how duplicate values are resolved and is the most common source of bugs — check it carefully.
• Classic applications: Next Greater/Smaller Element, Daily Temperatures, Largest Rectangle in Histogram, Stock Span, and Trapping Rain Water.