Monotonic Stack

A monotonic stack is an ordinary Stack augmented with a single invariant: the elements stored in it, read from bottom to top, are kept in monotonically non-decreasing (or, symmetrically, non-increasing) order. The invariant is enforced lazily, at every push: when adding a new element would violate monotonicity, the offending top elements are popped first. The pattern’s deep value is its complexity: even though each push can trigger a cascade of pops, each element is pushed at most once and popped at most once across the entire run, giving O(n) total, not the O(n²) a naive read of the inner-loop suggests. Monotonic stacks are the canonical tool for the “for each element, find the nearest larger/smaller element to the left/right” family of problems — including the stunningly elegant histogram-largest-rectangle (LC 84), trapping rainwater (LC 42), daily temperatures (LC 739), online stock span (LC 901), and sum of subarray minimums (LC 907).

1. Intuition — A Skyline of Decreasing Office Buildings

Picture standing on the roof of a building, looking out across a city skyline at successively shorter buildings stretching toward the horizon. Each building you can see blocks the buildings behind it that are not as tall — they’re hidden by the building in front. As you walk forward, every time you reach a building taller than what you can see ahead, the previously-visible shorter buildings behind you get blocked from your line of sight backward. The set of “currently visible from where I am, looking ahead” forms a strictly decreasing sequence of heights. That set is exactly what a monotonic decreasing stack maintains as you sweep through the input.

A second analogy useful for the “next greater element” framing: imagine a line of customers waiting at a deli counter. Each customer wants to know “who’s the next person taller than me ahead in line?” Customers stand in line; whenever a tall person joins the back, all the shorter people who were patiently waiting in front of them get their answer (“the new tall person is your next-greater-on-the-right”) and exit the unanswered queue. Each person joins the unanswered queue once and leaves once — total work bounded by O(n).

The deep reason this pattern delivers O(n): the monotonicity invariant means the stack contents always fit a single ordered structure, so the question “is the new element the answer for any waiting elements?” can be resolved by repeatedly inspecting the top — no rescanning, no random access into the middle. Each element waits in the stack until its answer arrives or until the input runs out; the total wait-and-resolve work is bounded by the total number of pushes, which is the number of input elements.

2. Tiny Worked Example — Next Greater Element to the Right

Given arr = [2, 1, 5, 3, 6, 4, 6], for each index i find arr[j] for the smallest j > i with arr[j] > arr[i]; output -1 if none exists. Expected: [5, 5, 6, 6, -1, 6, -1].

We sweep left to right, maintaining a stack of indices whose values are strictly decreasing top-to-bottom (equivalently, the values underneath are larger). When the new element arr[i] is greater than the value at the top of the stack, the top has found its next-greater-element — pop it and record arr[i] as its answer. Repeat until the top is no longer smaller, then push i.

i	arr[i]	Stack indices	Stack values	Action / Resolutions
0	2	[0]	[2]	push 0
1	1	[0, 1]	[2, 1]	top (1) < 2, push (top must be > new for monotonic dec; 1 < 2 means new element would violate? See note)
2	5	[2]	[5]	5 > 1: pop idx 1 → ans[1]=5. 5 > 2: pop idx 0 → ans[0]=5. push 2
3	3	[2, 3]	[5, 3]	3 < 5, push 3
4	6	[4]	[6]	6 > 3: pop idx 3 → ans[3]=6. 6 > 5: pop idx 2 → ans[2]=6. push 4
5	4	[4, 5]	[6, 4]	4 < 6, push 5
6	6	[4, 6]	[6, 6]	6 == 4? No, 6 > 4: pop idx 5 → ans[5]=6. 6 == 6 not strictly greater, push 6
end	—	[4, 6]	[6, 6]	unresolved indices 4 and 6: ans[4] = ans[6] = -1

Strict vs Non-strict Monotonicity

“Strict decreasing” is what we want for next strictly greater element. The stack is decreasing in the sense that pushed values are smaller than (or equal to) what’s below them as we go down. When a new element is greater than the top, it pops the top. When equal — convention dependent: if you want “next greater (strict)” only, treat equal as “still smaller” and don’t pop; if you want “next greater-or-equal,” pop on equality. Get this convention right or your answers shift by one for ties.

Final answers: [5, 5, 6, 6, -1, 6, -1] — matches expected. Total pushes: 7. Total pops: 5 (indices 1, 0, 3, 2, 5). Each element entered and exited the stack at most once; nothing was inspected beyond the top.

3. The Pattern Recognition Signal

Reach for a monotonic stack when any of these phrasings appears:

1. “For each element, find the nearest (greater | smaller | greater-or-equal | smaller-or-equal) element to the (left | right).” This is the textbook trigger. Four directions × two strictnesses = eight stock variants, all O(n) with a monotonic stack.

2. “For each position, how far back can I extend a streak where the current value is the (max | min)?” — Stock span (LC 901), histogram bar’s “left limit” and “right limit.”

3. “Compute, for each subarray, the (max | min), and aggregate.” — Sum of subarray minimums (LC 907) decomposes into “for each element, count subarrays where it is the min.”

4. “Find the largest rectangle / region whose height is bounded by the smallest element it contains.” — Histogram largest rectangle (LC 84), maximal-rectangle-in-binary-matrix (LC 85).

5. “Trapping water / containers / 2D water-pouring.” — Trapping rainwater (LC 42), with the per-column rule that water level = min(max-left, max-right), and the monotonic stack solves it in one pass.

6. Linear scan + “look back” with conditional updates that involve removing previously-seen elements. — The hint is whenever you would write for j in range(i): ... and conditionally process or skip, ask whether the j’s you keep form a monotone sequence.

The inverse signals — when monotonic stack is wrong:

• You need to track elements with non-monotone properties (e.g., the kth-largest in a window) — that’s heap / Two Heaps Pattern / sorted multiset territory.
• You need to handle deletions or queries from arbitrary positions, not just one end of the in-progress sweep — that’s Segment Tree or Fenwick Tree territory.
• The problem is on a static array and asks queries about arbitrary subranges — precompute or use sparse tables, not a single-pass stack.
• The values are not totally orderable (e.g., 2D points with no scalar comparison) — define a comparison or pick a different tool.

4. Pseudocode

The most-general “next greater element to the right” template:

next_greater_right(arr):                        # returns array of same length
    n := length(arr)
    result := array of n filled with NIL
    stack := empty stack of indices
    for i in 0 .. n - 1:
        while stack is not empty AND arr[stack.top()] < arr[i]:
            j := stack.pop()
            result[j] := arr[i]                 # arr[i] is j's answer
        stack.push(i)
    return result                               # NIL = no greater element to the right

Variants by direction and comparator:

• Next greater to the left: iterate left-to-right but record arr[stack.top()] as the answer for i before the while-pop, then pop while arr[top] <= arr[i] (or <), then push.
• Next smaller to the right: swap < for >. Stack becomes monotonically increasing.
• Strict vs non-strict: < vs <= flips strict. Pick by problem requirement.
• Histogram-style “left and right limits”: run two passes (or one cleverly) — for each bar, compute the index of the nearest strictly-shorter bar to the left and to the right; the bar’s “rectangle width with itself as min height” is right_limit - left_limit - 1.

Decision tree for which variant:

"For each i, find ___ element to the ___":
                          ↓
                ┌─────────┴─────────┐
                ↓                   ↓
           "to the right"      "to the left"
           sweep i=0..n-1      sweep i=0..n-1
           pop while top       pop while top
           is smaller than i   is smaller-or-equal to i
           assign ans[popped]  ans[i] = arr[top] (after pop)
           push i              push i

For “smaller” instead of “greater,” flip the comparator on the while-condition.

5. Python Implementations

5.1 Daily Temperatures (LeetCode 739)

For each day’s temperature, return the number of days until a warmer day, or 0 if no warmer day exists.

def daily_temperatures(temperatures: list[int]) -> list[int]:
    n = len(temperatures)
    answer = [0] * n
    stack: list[int] = []                      # indices of unresolved days
    for i, t in enumerate(temperatures):
        while stack and temperatures[stack[-1]] < t:
            j = stack.pop()
            answer[j] = i - j                  # days until warmer
        stack.append(i)
    return answer                              # entries left as 0 = no warmer day

The while stack and ... < t is the heart. Days waiting in the stack are in strictly decreasing temperature order from bottom to top (otherwise they’d have been popped already). When today’s temperature is warmer than the top, the top day finally has its answer. We continue popping until today is no longer warmer than the new top, then push today.

5.2 Next Greater Element II (LeetCode 503) — Circular Array

The same problem on a circular array (indexes wrap). The trick: simulate by iterating i from 0 to 2n - 1, using arr[i % n], and only push for i < n (avoid double-push but still allow late pops to resolve early elements).

def next_greater_elements_circular(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack: list[int] = []
    for i in range(2 * n):
        cur = nums[i % n]
        while stack and nums[stack[-1]] < cur:
            result[stack.pop()] = cur
        if i < n:
            stack.append(i)
    return result

The “double the input length” trick is a recurring pattern for circular-array problems. We never push the second-pass indices but we still let them trigger pops for unresolved first-pass indices — exactly the missing-from-naive-NGE behavior we want.

5.3 Largest Rectangle in Histogram (LeetCode 84)

Given bar heights heights[i] of unit width, find the area of the largest axis-aligned rectangle that fits within the bars. The bar at index i participates in a rectangle of height heights[i] whose width is right_limit[i] - left_limit[i] - 1, where left_limit[i] is the index of the nearest strictly shorter bar to the left (or -1), and right_limit[i] is the same to the right (or n). The maximum rectangle is max over i of heights[i] × (right_limit[i] - left_limit[i] - 1).

The single-pass O(n) algorithm fuses both limit computations:

def largest_rectangle(heights: list[int]) -> int:
    n = len(heights)
    stack: list[int] = []                      # strictly increasing heights' indices
    best = 0
    for i in range(n + 1):                     # +1 to flush at the end
        cur = 0 if i == n else heights[i]
        while stack and heights[stack[-1]] > cur:
            h = heights[stack.pop()]
            # right_limit = i (current), left_limit = new top after pop, or -1 if empty
            left_limit = stack[-1] if stack else -1
            width = i - left_limit - 1
            best = max(best, h * width)
        stack.append(i)
    return best

The dummy “height 0 at index n” forces all remaining stack elements to flush at the end — they each get a definite right limit (n) and their left limits from the earlier stack contents. Beautifully terse, ferociously hard to derive from first principles, and an undisputed interview classic. The Barbay–Navarro analysis (2008) gives an information-theoretic lower bound matching this O(n).

5.4 Trapping Rain Water (LeetCode 42)

Given heights, water can collect in a “valley” between two taller bars. Naive: for each column, find max-left and max-right, water above column = min(max_left, max_right) - height[i] if positive. The monotonic-stack approach computes the trapped water directly by treating each “horizontal layer” between rising bars:

def trap(heights: list[int]) -> int:
    stack: list[int] = []                      # strictly decreasing heights' indices
    water = 0
    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            left = stack[-1]
            width = i - left - 1
            bounded_height = min(heights[left], h) - heights[bottom]
            water += width * bounded_height
        stack.append(i)
    return water

Each pop represents the “valley floor” between the new tall bar (right wall) and the pre-existing tall bar (left wall). Water collected on top of that floor is width × bounded_height. Total trapped water accumulates across all such pops. There’s an alternative two-pointer solution to the same problem in O(n) and O(1) space; the monotonic-stack version uses O(n) auxiliary space but generalizes to less-symmetric height patterns. See Two Pointers for the alternative.

5.5 Sum of Subarray Minimums (LeetCode 907)

Compute sum over all subarrays of arr of min(subarray), modulo 10⁹ + 7. The cute trick: for each element arr[i], count the number of subarrays in which it is the minimum, then multiply by arr[i] and sum.

arr[i] is the minimum of subarrays whose left endpoint is in (prev_less_or_equal[i], i] and whose right endpoint is in [i, next_less[i]). Define:

• left[i] = index of nearest element to the left strictly less than (or less-or-equal-to, by tie-breaking convention) arr[i], or -1.
• right[i] = index of nearest element to the right strictly less than arr[i], or n.

Number of subarrays in which arr[i] is the minimum = (i - left[i]) × (right[i] - i).

MOD = 10**9 + 7
 
def sum_subarray_mins(arr: list[int]) -> int:
    n = len(arr)
    left = [-1] * n
    right = [n] * n
    stack: list[int] = []
    for i in range(n):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        left[i] = stack[-1] if stack else -1
        stack.append(i)
    stack.clear()
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] >= arr[i]:   # note: >= to break ties consistently
            stack.pop()
        right[i] = stack[-1] if stack else n
        stack.append(i)
    total = 0
    for i in range(n):
        total = (total + arr[i] * (i - left[i]) * (right[i] - i)) % MOD
    return total

The asymmetric > on the left scan and >= on the right scan is the tie-breaking discipline that ensures each subarray with multiple equal minima is counted exactly once (attributed to its leftmost occurrence). Get this wrong and you double-count subarrays with duplicate-min elements. This is a notorious bug-magnet, and the “asymmetric strictness” trick is the single insight that unlocks correctness.

5.6 Online Stock Span (LeetCode 901)

The streaming version: each call to next(price) returns the number of consecutive days (counting today) where price was ≤ today’s price. Maintain a stack of (price, span) pairs:

class StockSpanner:
    def __init__(self) -> None:
        self._stack: list[tuple[int, int]] = []   # (price, span)
 
    def next(self, price: int) -> int:
        span = 1
        while self._stack and self._stack[-1][0] <= price:
            _, prev_span = self._stack.pop()
            span += prev_span
        self._stack.append((price, span))
        return span

The stack stores compressed runs: when today swallows several past days, those days’ contributions sum into today’s span. The amortized O(1) per call comes from the same “each element pushed and popped at most once” argument.

6. Complexity — The Amortized O(n) Argument

Time: O(n) total across the entire algorithm, even though there’s a while loop nested inside a for loop.

The proof is the aggregate method of amortized analysis. Define the potential Φ as the current size of the stack. Each iteration of the outer for loop performs:

• Some number of pops (say, k_i at iteration i).
• Exactly one push.

The cost of iteration i is 1 + k_i. The change in potential is +1 - k_i (one push minus k_i pops). The amortized cost of iteration i is

amortized_i = real_cost_i + ΔΦ_i = (1 + k_i) + (1 - k_i) = 2

So each iteration’s amortized cost is constant (= 2). Across n iterations, total real cost ≤ total amortized cost = 2n. Plus the final flush of the stack (≤ n more pops) gives total cost ≤ 3n = O(n).

The deeper invariant: each input element is pushed at most once and popped at most once. Total pushes = n; total pops ≤ n. Other work (assignments, comparisons) is O(1) per push/pop. So total work = O(n).

This argument is identical in spirit to the Two Pointers argument for a same-direction sweep — both rely on a monotone counter (here: stack position over time, in two-pointers: the trailing pointer’s position) being bounded.

Space: O(n) worst-case for the stack (a strictly monotone input forces every element to remain on the stack simultaneously). For example, on a strictly decreasing input [5, 4, 3, 2, 1], the next-greater-right algorithm pushes all five and pops nothing, peaking at full size.

The O(n) time bound is tight — it cannot be improved because the algorithm must at minimum read every input element. Any monotonic-stack problem variant therefore matches this lower bound.

7. Variants and Sub-patterns

7.1 Maximum Rectangle in Binary Matrix (LeetCode 85)

For each row, treat it as the base of a histogram of “consecutive 1s above this cell, including this cell.” Run LeetCode 84’s algorithm on each row’s histogram. Total O(rows × cols).

7.2 Maximal Rectangle of 1s (multiple variants)

Generalizes the histogram trick to many 2D shape-extremum problems. Always: project to a 1D histogram per row, then run the monotonic-stack rectangle algorithm.

7.3 Removing K Digits to Minimize (LeetCode 402)

Greedy “remove a digit when the next is smaller” — a monotonic non-decreasing stack of remaining digits. Each input digit is pushed once and popped at most once, O(n).

7.4 Maximum Sliding-Window Sum with Constraint

Some problems require the maximum of f(i, j) = arr[i] - arr[j] for i > j — equivalent to “for each i, find the smallest preceding element,” a monotonic-stack lookup.

7.5 Build the Lexicographically Smallest Subsequence (LeetCode 316/1081)

Maintain a non-decreasing stack of selected characters; pop a previously-selected character if it’s larger than the current and we still have copies of it to the right. The “still available later” check is what distinguishes this from naive monotonic stack.

8. Pitfalls

8.1 Strict vs Non-Strict Comparator

< vs <= in the while-condition flips between strict and non-strict variants. “Next strictly greater” needs <; “next greater-or-equal” needs <=. Get the wrong one and your answers shift by one for every tie. Doubly evil because the bug only surfaces on inputs containing equal values.

8.2 Tie-Breaking in Subarray-Counting Problems

For subarray-minimum-sum (LC 907) and friends, you must pick which of the equal-value indices “owns” each subarray with duplicate minima. The asymmetric > / >= strictness on the two sweeps is the standard fix; mishandling it double-counts or miscounts subarrays.

8.3 Forgetting to Flush the Stack

After the main loop, elements still on the stack have “no answer” — they need to be assigned the sentinel (-1, n, 0, depending on the problem). The “+1 dummy iteration with sentinel value” trick (used in §5.3 for histogram) automates this flush; otherwise add an explicit post-loop drain.

8.4 Storing Values Instead of Indices

In some problems you only need values, but in many — especially anything involving distance like LC 739 (“how many days”) — you need the index of the popped element to compute i - j. Push indices, not values; values are recovered via arr[stack[-1]].

8.5 Confusing “Next Greater” with “Greatest Following”

“Next greater” means the first greater element after i, not the largest element after i. The largest-element-suffix problem is solved by a single backward pass with running max — no stack needed. Read the problem precisely.

8.6 Pushing Before the Pops Are Done

The classical bug: stack.append(i) before the while that pops. This breaks monotonicity and silently corrupts answers. Always: pop first, then push.

8.7 Misjudging Whether the Pattern Applies

If the predicate involves more than two values (e.g., “find the smallest pair-sum to the right”), monotonic stack alone does not suffice. The pattern works exactly when the answer for an element depends on the next element satisfying a monotone comparison.

8.8 Off-By-One in the Histogram Width

width = right - left - 1 (not right - left). The boundaries left and right are outside the rectangle (they’re the indices of the strictly-smaller neighbors). The number of bars between them, exclusive, is right - left - 1. A common one-off bug.

9. Diagram — Monotonic Stack Sweep on [3, 1, 4, 1, 5, 9, 2, 6]

flowchart TD
    S0["i=0, x=3\nstack=[]\npush 0\nstack=[0(3)]"]
    S1["i=1, x=1\ntop=3 > 1, no pop\npush 1\nstack=[0(3),1(1)]"]
    S2["i=2, x=4\n4 > 1: pop 1, ans[1]=4\n4 > 3: pop 0, ans[0]=4\npush 2\nstack=[2(4)]"]
    S3["i=3, x=1\ntop=4 > 1, no pop\npush 3\nstack=[2(4),3(1)]"]
    S4["i=4, x=5\n5 > 1: pop 3, ans[3]=5\n5 > 4: pop 2, ans[2]=5\npush 4\nstack=[4(5)]"]
    S5["i=5, x=9\n9 > 5: pop 4, ans[4]=9\npush 5\nstack=[5(9)]"]
    S6["i=6, x=2\ntop=9 > 2, no pop\npush 6\nstack=[5(9),6(2)]"]
    S7["i=7, x=6\n6 > 2: pop 6, ans[6]=6\n6 < 9, no further pop\npush 7\nstack=[5(9),7(6)]"]
    S8["END\nremaining: 5(9), 7(6) → ans[5]=ans[7]=-1"]
    S0 --> S1 --> S2 --> S3 --> S4 --> S5 --> S6 --> S7 --> S8

What this diagram shows. The full sweep of the next-greater-element-to-the-right algorithm on [3, 1, 4, 1, 5, 9, 2, 6]. Each box reports the iteration index i and value x, the popping decisions, and the resulting stack (each entry is idx(value)). Notice that the stack at every step holds indices whose values, read top to bottom, are monotonically increasing downward (or strictly decreasing top-to-bottom) — that’s the invariant. The total number of pops across the run is 5 (matching the elements that get an answer); the unresolved remainders (indices 5 and 7) get the sentinel -1. Final answers: [4, 4, 5, 5, 9, -1, 6, -1]. The “each element pushed once, popped once” property is visually obvious: every box adds one element to the stack and removes some prefix from the top, never reaching into the middle.

10. Common Interview Problems

#	Problem	Variant
LC 84	Largest Rectangle in Histogram	Two-sided nearest smaller
LC 85	Maximal Rectangle	Per-row histogram + LC 84
LC 42	Trapping Rain Water	Layer-by-layer water
LC 11	Container With Most Water	(Two-pointer; not monotonic stack — included as a contrast)
LC 496	Next Greater Element I	Map + nearest-greater
LC 503	Next Greater Element II	Circular array, double-loop trick
LC 739	Daily Temperatures	Distance to next greater
LC 901	Online Stock Span	Streaming, compressed runs
LC 907	Sum of Subarray Minimums	Each element’s “ownership count”
LC 2104	Sum of Subarray Ranges	LC 907 doubled (max - min)
LC 402	Remove K Digits	Greedy non-decreasing stack
LC 316 / 1081	Remove Duplicate Letters / Smallest Subsequence	Lex-smallest with availability
LC 1019	Next Greater Node In Linked List	LC 503 over a linked list
LC 962	Maximum Width Ramp	Decreasing stack + reverse scan
LC 1762	Buildings With an Ocean View	Right-to-left monotonic
LC 768	Max Chunks To Make Sorted II	Increasing stack of running maxes

11. Open Questions

• Can monotonic stack be generalized to two dimensions in a way that beats per-row decomposition? Existing 2D variants reduce back to 1D; a true 2D O(n²) histogram method exists (LC 85) but I’m not aware of a sub-O(n²) approach for arbitrary 2D nearest-neighbor problems.
• What is the exact relationship between monotonic stacks and Cartesian trees? Building a Cartesian tree from an array is O(n) using the same monotonic-stack pattern; “least common ancestor in Cartesian tree” answers many of the same range-min queries that monotonic stacks resolve in single-pass form.
• In streaming / online settings (when the array isn’t fully known in advance), the monotonic-stack pattern works for “next greater element to the left” but not “to the right” — the right-side problem fundamentally requires seeing the future. Are there approximate / probabilistic algorithms for the streaming-right-side variant?

12. See Also

• Stack — the underlying data structure
• Monotonic Deque — sister pattern for sliding-window min/max (front and back operations)
• Sliding Window — overlaps with monotonic stack on some problems
• Two Pointers — alternative to monotonic stack for some symmetric problems (e.g., trapping rain water in O(1) space)
• Binary Heap — alternative when monotone constraint doesn’t hold
• Big-O Notation — for the amortized argument
• SWE Interview Preparation MOC