Monotonic Stack

Any time you catch yourself writing a nested loop to find “the next bigger value to the right” or “how far until something taller shows up”, stop — there’s a one-pass, $O(n)$ trick for it. A monotonic stack keeps only the indices that could still matter, discarding the rest the instant a new element proves them irrelevant.

What you’ll learn

The cue: “next greater element”, “next smaller element”, “days until warmer”, or anything about comparing each element to what comes after it.
The template: a stack of indices that stays increasing (or decreasing) in value, popped whenever the incoming element breaks that order.
Why every index is pushed and popped at most once, giving $O(n)$ total despite the whilewhile loop inside the forfor loop.
How the same idea extends to histogram-area and rainwater-trapping problems.

The pattern: a decreasing stack for “next greater”

Keep a stack of indices, where the corresponding values are always decreasing from bottom to top. When a new value arrives that’s bigger than the value at the top of the stack, that new value is the “next greater element” for everything it pops — so pop them all, recording the answer for each, before pushing the new index.

next_greater_element.py

def next_greater_elements(nums):
    n = len(nums)
    result = [-1] * n     # default: no greater element exists
    stack = []             # indices, values decreasing bottom-to-top
 
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x     # x is the next greater element for this popped index
        stack.append(i)
 
    return result
 
 
nums = [2, 1, 2, 4, 3]
print(next_greater_elements(nums))   # expect [4, 2, 4, -1, -1]

next_greater_element.py

def next_greater_elements(nums):
    n = len(nums)
    result = [-1] * n     # default: no greater element exists
    stack = []             # indices, values decreasing bottom-to-top
 
    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            result[stack.pop()] = x     # x is the next greater element for this popped index
        stack.append(i)
 
    return result
 
 
nums = [2, 1, 2, 4, 3]
print(next_greater_elements(nums))   # expect [4, 2, 4, -1, -1]

Every index enters the stack exactly once (one appendappend per loop iteration) and leaves it at most once (one poppop total, ever, per index) — so despite the nested whilewhile, the total work across the whole function is $O(n)$ , not $O(n^2)$ .

How it works

sketch A decreasing monotonic stack scanning [2, 1, 2, 4, 3] p5.js

Each bar's index is pushed onto the stack. A new, taller bar pops every shorter bar still on the stack -- each pop resolves that index's 'next greater element'.

Worked example: Daily Temperatures

“How many days until a warmer temperature?” is the exact same pattern with the answer reframed as a distance (i - ji - j) instead of the popped value itself.

daily_temperatures.py

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n       # default: no warmer day ever comes
    stack = []              # indices, temperatures decreasing bottom-to-top
 
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j     # how many days until it got warmer
        stack.append(i)
 
    return result
 
 
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))   # expect [1, 1, 4, 2, 1, 1, 0, 0]

daily_temperatures.py

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n       # default: no warmer day ever comes
    stack = []              # indices, temperatures decreasing bottom-to-top
 
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            result[j] = i - j     # how many days until it got warmer
        stack.append(i)
 
    return result
 
 
temps = [73, 74, 75, 71, 69, 72, 76, 73]
print(daily_temperatures(temps))   # expect [1, 1, 4, 2, 1, 1, 0, 0]

Extending it: increasing stack for histogram area

Flip the invariant to an increasing stack (indices with values increasing bottom-to-top) and you get the classic Largest Rectangle in Histogram: when a bar shorter than the stack’s top arrives, that bar caps how far every taller bar above it could have stretched, so pop and price each one out.

largest_rectangle_histogram.py

def largest_rectangle_area(heights):
    stack = []       # indices, heights increasing bottom-to-top
    max_area = 0
 
    for i, h in enumerate(heights + [0]):   # sentinel 0 flushes the stack at the end
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
 
    return max_area
 
 
print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))   # expect 10

largest_rectangle_histogram.py

def largest_rectangle_area(heights):
    stack = []       # indices, heights increasing bottom-to-top
    max_area = 0
 
    for i, h in enumerate(heights + [0]):   # sentinel 0 flushes the stack at the end
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)
 
    return max_area
 
 
print(largest_rectangle_area([2, 1, 5, 6, 2, 3]))   # expect 10

Trapping Rain Water can be solved the same way too: a decreasing stack of indices, where popping a “valley” bar lets you compute the water trapped above it, bounded by the shorter of its left and right walls.

Time and space complexity

Operation	Complexity
Next greater/smaller element, one pass	$O(n)$ time — each index pushed and popped once
Daily Temperatures	$O(n)$ time
Largest Rectangle in Histogram	$O(n)$ time
Space (the stack itself)	$O(n)$ worst case

When to use it

The question is phrased as “next greater/smaller element” or “distance until a bigger/smaller value appears” — a brute-force nested loop is $O(n^2)$ , a monotonic stack is $O(n)$ .
You’re computing areas or bounded regions defined by heights — histogram bars, skyline problems, rainwater trapped between bars — where each bar’s contribution depends on the nearest taller bar on each side.
You need, for every index, the nearest index to the left or right that breaks some ordering — the stack always holds exactly the candidates that haven’t been “resolved” yet.

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output — then paste the same code into leetcode.com.

LC 496 — Next Greater Element I · Easy

Problem. nums1nums1 is a subset of nums2nums2. For each value in nums1nums1, find the next greater element to its right in nums2nums2, or -1-1 if none exists.

Constraints. 1 <= len(nums1) <= len(nums2) <= 10001 <= len(nums1) <= len(nums2) <= 1000, all values unique within each array.

Examples. nums1 = [4,1,2], nums2 = [1,3,4,2]nums1 = [4,1,2], nums2 = [1,3,4,2] gives [-1,3,-1][-1,3,-1] · nums1 = [2,4], nums2 = [1,2,3,4]nums1 = [2,4], nums2 = [1,2,3,4] gives [3,-1][3,-1]

Editorial — approach, complexity, follow-ups

Maintain a stack of values still waiting for a greater element, kept decreasing. A new value resolves every smaller value on the stack at once, because it is the first greater element for all of them.

Time $O(n + m)$ — each value is pushed once and popped at most once. Space $O(n)$ .

Values still on the stack at the end never found anything greater, which is exactly what nxt.get(n, -1)nxt.get(n, -1) expresses — no explicit flush needed.

Keying by value works only because the problem guarantees uniqueness. With duplicates you must key by index, which is what LC 739 does.

Follow-ups you should expect: “Circular array (LC 503)?” — iterate twice over the array (or over nums * 2nums * 2) so later elements can wrap around, pushing only on the first pass. “Duplicates allowed?” — store indices instead of values. “Next smaller element?” — flip the comparison to an increasing stack. “Previous greater element?” — sweep right to left.

LC 739 — Daily Temperatures · Medium

Problem. Given daily temperatures, return an array where answer[i]answer[i] is the number of days you must wait after day ii for a warmer temperature. If no warmer day exists, put 00.

Constraints. 1 <= len(temperatures) <= 10^51 <= len(temperatures) <= 10^5, 30 <= temperatures[i] <= 10030 <= temperatures[i] <= 100.

Examples. [73,74,75,71,69,72,76,73][73,74,75,71,69,72,76,73] gives [1,1,4,2,1,1,0,0][1,1,4,2,1,1,0,0] · [30,40,50,60][30,40,50,60] gives [1,1,1,0][1,1,1,0] · [30,60,90][30,60,90] gives [1,1,0][1,1,0]

Editorial — approach, complexity, follow-ups

Exactly LC 496’s sweep, with two adaptations: the stack holds indices so the answer can be a distance, and the output is pre-filled with 00 so days that never find a warmer one need no special handling.

Time $O(n)$ — each index pushed once, popped at most once. Space $O(n)$ .

The reason this beats the $O(n^2)$ nested scan is that a colder day sitting under a warmer one on the stack can never be the answer for anything to the right — the warmer day would resolve it first. So each index only needs to be considered once.

Because temperatures may repeat, the comparison is strict (< t< t): an equal temperature is not warmer, so it must not resolve the day beneath it. That is why indices rather than values are needed here where LC 496 could use values.

Follow-ups you should expect: “Do it right to left instead?” — also works, and you can skip forward using already-computed answers. “Previous warmer day?” — sweep in the other direction. ” $O(1)$ space?” — not possible in general; you must remember unresolved days. “Why does the stack stay decreasing?” — anything that would break the order is popped first, by construction.

LC 84 — Largest Rectangle in Histogram · Hard

Problem. Given bar heights of width 1 each, return the area of the largest rectangle that fits inside the histogram.

Constraints. 1 <= len(heights) <= 10^51 <= len(heights) <= 10^5, 0 <= heights[i] <= 10^40 <= heights[i] <= 10^4.

Examples. [2,1,5,6,2,3][2,1,5,6,2,3] gives 1010 (heights 5 and 6, width 2) · [2,4][2,4] gives 44 · [5,4,3,2,1][5,4,3,2,1] gives 99

Editorial — approach, complexity, follow-ups

Every maximal rectangle is limited by some bar’s height. For each bar, the widest rectangle at that height extends left and right until it meets something shorter.

An increasing stack finds both boundaries at the right moment: when a bar is popped because a shorter bar arrived, the right boundary is the current index, and the left boundary is just past whatever is now on top of the stack — which is the nearest shorter bar to its left.

Time $O(n)$ . Space $O(n)$ .

Three details:

The sentinel 00. Iterating heights + [0]heights + [0] guarantees every remaining bar is popped and priced. Without it, an increasing histogram like [2,4][2,4] leaves everything on the stack unpriced and returns 00.
left = stack[-1] + 1 if stack else 0left = stack[-1] + 1 if stack else 0. An empty stack means nothing shorter exists to the left, so the rectangle reaches index 00.
>=>= rather than >>. With equal heights, popping the earlier one is safe: it will be re-priced through the later equal bar, which has the same height and a wider span. [2,2,2][2,2,2] giving 66 confirms it.

[5,4,3,2,1][5,4,3,2,1] giving 99 is a good trace — the answer is height 3 across width 3, found mid-sweep rather than at a boundary.

Follow-ups you should expect: “Maximal Rectangle in a binary matrix (LC 85)?” — build a histogram per row (heights of consecutive ones above) and run this on each row; $O(mn)$ overall. “Why >=>= and not >>?” — the equal-heights argument. “Trapping Rain Water (LC 42)?” — related but the geometry differs: you accumulate water above each position rather than rectangles beneath. “Divide and conquer?” — recurse on the minimum bar; $O(n \log n)$ average but $O(n^2)$ worst case.

LeetCode problem set

#	Problem	Difficulty	The twist
496	Next Greater Element I	Easy	The exact decreasing-stack template (II adds a circular array twist)
503	Next Greater Element II	Medium	The exact decreasing-stack template (II adds a circular array twist)
739	Daily Temperatures	Medium	Next-greater-element, answering with a distance instead of a value
84	Largest Rectangle in Histogram	Hard	The increasing-stack variant, pricing out each bar’s maximal rectangle as it gets popped
42	Trapping Rain Water	Hard	A decreasing stack of “walls”, computing water trapped above each popped valley
907	Sum of Subarray Minimums	Medium	For each element, use a monotonic stack to find how many subarrays it’s the minimum of, then sum `value * countvalue * count` over all elements

Recap

A monotonic stack holds indices in increasing or decreasing order of their values, popping whenever a new element breaks that order.
Decreasing stack -> “next greater element” style questions. Increasing stack -> histogram/area style questions where a short bar caps taller ones.
Every index is pushed once and popped at most once, so the total work is $O(n)$ even with a whilewhile loop nested inside the main forfor loop.
The same scaffolding solves next-greater/smaller, daily temperatures, histogram area, rainwater trapping, and subarray-minimum-sum questions — only what you compute on a pop changes.

Next: Prefix Sums and Difference Arrays — answering range-sum queries in $O(1)$ after a single $O(n)$ preprocessing pass.

If this helped you, consider buying me a coffee ☕

Buy me a coffee

Monotonic Stack

What you’ll learn

The pattern: a decreasing stack for “next greater”

How it works

Worked example: Daily Temperatures

Extending it: increasing stack for histogram area

Time and space complexity

When to use it

Practice — real LeetCode problems

LC 496 — Next Greater Element I · Easy

LC 739 — Daily Temperatures · Medium

LC 84 — Largest Rectangle in Histogram · Hard

LeetCode problem set

Recap

Was this page helpful?