patternDSA/Monotonic Stack
Core Pattern → Pattern 14

Monotonic Stack

A stack with a rule: values are always non-increasing or non-decreasing. Each element enters once and leaves once — giving O(n) solutions to problems that look like they need O(n²) comparisons.

Frequency:★★★★☆
·~35 min·Intermediate·7 problems
The Core Shock

Find next greater for every element with nested loops — O(n²). Monotonic stack — O(n)

Brute Force
O(n²)
Nested loops: for each element scan right
Sorting
O(n log n)
Doesn't preserve position information
Monotonic Stack
O(n)
Each element pushed & popped at most once

The invariant: the stack is always sorted. When a new element violates the sort order, pop everything it violates — those elements have just found their answer (the current element). Each element enters once and leaves once → 2n ops → O(n).

Two Monotonic Stack Types

The direction of the invariant determines what question you're answering.

Decreasing Stack
Stack values non-increasing (bottom→top)

Elements wait on the stack until something larger arrives. That larger element IS their next greater. Popping resolves them.

Pop condition: Pop when current > stack top
Daily TemperaturesNext Greater ElementRemove Nodes From Linked ListLargest Rectangle in HistogramTrapping Rain Water
Increasing Stack
Stack values non-decreasing (bottom→top)

Elements wait until something smaller arrives (for next-smaller). Or greedily remove larger elements to minimize a number.

Pop condition: Pop when current < stack top
Remove K DigitsSum of Subarray MinimumsRemove All Adjacent Duplicates132 PatternStock Span

The 3-Step Framework

The same skeleton works for every monotonic stack problem.

01
Choose direction: increasing or decreasing?

Decreasing: 'next/previous GREATER element', 'how long until X exceeds Y', 'largest rectangle'. Increasing: 'next/previous SMALLER element', 'smallest possible result', 'remove large elements greedily'.

# Next GREATER -> decreasing stack
# while stack and nums[stack[-1]] < nums[i]:

# Next SMALLER -> increasing stack
# while stack and nums[stack[-1]] > nums[i]:
When in doubt, ask: 'does a new LARGER element resolve waiting items (decreasing) or does a new SMALLER element resolve them (increasing)?'
02
The pop loop: resolve and record

Inside the while loop: pop the index, compute the answer for that index (usually using the current index for distance or current value for NGE), write to result. Then push the current index.

while stack and nums[stack[-1]] < nums[i]:  # decreasing
    idx = stack.pop()
    result[idx] = nums[i]     # current = NGE
    # or: result[idx] = i - idx  # distance
stack.append(i)             # push index (not value)
Always push the INDEX, not the value. You need the index to: (1) write result[idx], and (2) compute distance (i - idx).
03
After the loop: handle remaining stack

Elements remaining on the stack after the loop have no next greater/smaller — leave result at default (-1 or 0). For Remove K Digits: trim k from end. For contribution problems: boundaries are array edges.

# NGE: remaining have no NGE, result stays -1
return result

# Remove K Digits: k removals still needed
if k: stack = stack[:-k]
return ''.join(stack).lstrip('0') or '0'
The default value in result initialization matters. For 'days until warmer': default 0 (never). For NGE: default -1 (none). Initialize correctly before the loop.

Pattern Recognition

Two seconds to identify monotonic stack in an interview.

Use Monotonic Stack When
"Next/Previous Greater/Smaller element"
"How many days until temperature rises"
Remove elements to minimize or maximize result
"Sum/product of subarray mins/maxes"
Largest rectangle or area problems
Stock span, profit maximization problems
Remove adjacent duplicates (with count)
Any problem needing left and right boundaries simultaneously
Common Pitfalls
Pushing values not indices → can't write result[idx]
Wrong direction: decreasing when need increasing
Strict vs non-strict: < vs <= affects duplicates
Remove K Digits: forgetting to trim if k > 0 after loop
Remove K Digits: forgetting lstrip('0') or '0' fallback
Sum of subarray mins: double-counting duplicates (use >= on one side)
Circular NGE: must loop twice (2*n) with i%n
Adjacent duplicates: use (char, count) tuples on stack