Monotonic Stack

What Is a Monotonic Stack?

A monotonic stack is a stack that maintains its elements in strictly monotonic order — either always increasing (bottom to top) or always decreasing. When a new element violates the monotonic property, elements are popped until the property is restored, then the new element is pushed.

MONOTONIC DECREASING STACK (each element ≤ element below it):
  Elements enter: 5, 3, 8, 4, 2, 7

  Push 5:  stack = [5]
  Push 3:  3 < 5 → ok         stack = [5, 3]
  Push 8:  8 > 3 → pop 3      3 < 5 → ok
           8 > 5 → pop 5      stack empty → push 8
                               stack = [8]
  Push 4:  4 < 8 → ok         stack = [8, 4]
  Push 2:  2 < 4 → ok         stack = [8, 4, 2]
  Push 7:  7 > 2 → pop 2
           7 > 4 → pop 4
           7 < 8 → ok → push  stack = [8, 7]

At any point, the stack is always in decreasing order (top to bottom).
The key insight: every pop event means "current element is greater than popped element."
That relationship is the answer to "Next Greater Element."

The pop events carry information. Every time an element is popped, the element that caused the pop is the answer to that popped element's query.

Two Variants

MONOTONIC DECREASING STACK:
  Maintain: stack[bottom] ≥ ... ≥ stack[top]
  Pop when: new element ≥ top (violates decreasing order)
  Captures: "current element is GREATER THAN popped element"
  Solves:   Next Greater Element, Daily Temperatures, Stock Span

MONOTONIC INCREASING STACK:
  Maintain: stack[bottom] ≤ ... ≤ stack[top]
  Pop when: new element ≤ top (violates increasing order)
  Captures: "current element is SMALLER THAN popped element"
  Solves:   Next Smaller Element, Largest Rectangle in Histogram (left boundary)

Recognition signal: "Find the next/previous greater/smaller element for each position"
                    or any problem where you need to know what's the first larger/smaller
                    value to the left or right of each element.

Problem 1: Next Greater Element — Monotonic Decreasing Stack

Problem: For each element in the array, find the next element to its right that is strictly greater. Return -1 if none exists.

Why monotonic stack: As we scan left to right, we want to know "when will each unresolved element get its answer?" The answer arrives the moment we see a larger element — exactly the moment we would pop it from a decreasing stack.

Output:
[5, 25, 25, -1]
[-1, 12, 12, -1]
[-1, -1, -1, -1, -1]
[2, 3, 4, 5, -1]

Circular:
[2, -1, 2]
[-1, 2, 3]

Dry Run: [4, 5, 2, 25]

result=[-1,-1,-1,-1], stack=[]

i=0, nums[0]=4:
  stack empty → push 0       stack=[0]

i=1, nums[1]=5:
  5 > nums[0]=4 → result[0]=5, pop 0   stack=[]
  stack empty → push 1                  stack=[1]   result=[5,-1,-1,-1]

i=2, nums[2]=2:
  2 > nums[1]=5? No → push 2            stack=[1,2]

i=3, nums[3]=25:
  25 > nums[2]=2 → result[2]=25, pop 2  stack=[1]   result=[5,-1,25,-1]
  25 > nums[1]=5 → result[1]=25, pop 1  stack=[]    result=[5,25,25,-1]
  stack empty → push 3                  stack=[3]

End: index 3 still in stack → result[3] stays -1

Final: [5, 25, 25, -1] ✓

Time: O(n) — each index pushed and popped at most once.

Problem 2: Daily Temperatures

Problem: Given an array of daily temperatures, for each day find how many days until a warmer temperature. Return 0 if there is no future warmer day.

Same pattern as Next Greater Element — but the answer is the index difference rather than the value itself.

Output:
[1, 1, 4, 2, 1, 1, 0, 0]
[1, 1, 1, 0]
[1, 1, 0]
[0, 0, 0]

Dry Run: [73, 74, 75, 71, 69, 72, 76, 73]

result=[0,0,0,0,0,0,0,0], stack=[]

i=0, temp=73: push 0              stack=[0]
i=1, temp=74: 74>73→result[0]=1-0=1, pop   stack=[1]   result=[1,...]
i=2, temp=75: 75>74→result[1]=2-1=1, pop   stack=[2]   result=[1,1,...]
i=3, temp=71: 71<75→push 3                 stack=[2,3]
i=4, temp=69: 69<71→push 4                 stack=[2,3,4]
i=5, temp=72: 72>69→result[4]=5-4=1, pop   stack=[2,3]
              72>71→result[3]=5-3=2, pop   stack=[2]
              72<75→push 5                 stack=[2,5]  result=[1,1,0,2,1,...]
i=6, temp=76: 76>72→result[5]=6-5=1, pop   stack=[2]
              76>75→result[2]=6-2=4, pop   stack=[]
              push 6                        stack=[6]   result=[1,1,4,2,1,1,...]
i=7, temp=73: 73<76→push 7                 stack=[6,7]

End: indices 6 and 7 remain → result stays 0

Final: [1,1,4,2,1,1,0,0] ✓

Problem 3: Stock Span Problem

Problem: For each day's stock price, find the span — the number of consecutive days (including today) going backwards where the price was ≤ today's price.

Monotonic decreasing stack insight: The span ends at the most recent day with a higher price. That previous higher price is the first element that would NOT be popped when today's price arrives on a decreasing stack.

Output:
[1, 1, 1, 2, 1, 4, 6]
[1, 1, 2, 4, 5, 1]
[1, 2, 3, 4, 5]

Dry Run: [100, 80, 60, 70, 60, 75, 85]

stack=[], span=[]

i=0, price=100: stack empty → span[0]=0+1=1,  push 0  stack=[0]
i=1, price=80:  80≤100? No → stack top=0(100)
                stack not empty → span[1]=1-0=1, push 1 stack=[0,1]
i=2, price=60:  60≤80? No → span[2]=2-1=1,  push 2  stack=[0,1,2]
i=3, price=70:  70≤60→ pop 2
                70≤80? No → span[3]=3-1=2,  push 3  stack=[0,1,3]
i=4, price=60:  60≤70? No → span[4]=4-3=1,  push 4  stack=[0,1,3,4]
i=5, price=75:  75≤60→ pop 4
                75≤70→ pop 3
                75≤80? No → span[5]=5-1=4,  push 5  stack=[0,1,5]
i=6, price=85:  85≤75→ pop 5
                85≤80→ pop 1
                85≤100? No → span[6]=6-0=6, push 6  stack=[0,6]

Final: [1,1,1,2,1,4,6] ✓

Interpretation: On day 6 (price=85), the last day with a higher
price was day 0 (price=100). So 6-0=6 days of consecutive ≤85.

Problem 4: Largest Rectangle in Histogram

Problem: Given an array of bar heights, find the area of the largest rectangle that fits within the histogram.

Monotonic increasing stack insight: For each bar, the largest rectangle using that bar as the shortest bar extends left to the first bar shorter than it and right to the first bar shorter than it. The stack maintains indices of increasing heights — when a shorter bar arrives, all taller bars that can no longer extend right are resolved.

Output:
10
4
16
1
20

Dry Run: [2, 1, 5, 6, 2, 3] → max area = 10

heights=[2,1,5,6,2,3], sentinel 0 appended conceptually
stack=[], maxArea=0

i=0, h=2: stack empty → push 0   stack=[0]
i=1, h=1: 1 < heights[0]=2
  pop 0: height=2, stack empty → width=1, area=2×1=2  maxArea=2
  push 1                         stack=[1]
i=2, h=5: 5>1 → push 2           stack=[1,2]
i=3, h=6: 6>5 → push 3           stack=[1,2,3]
i=4, h=2: 2 < heights[3]=6
  pop 3: height=6, left=2(stack top)→ width=4-2-1=1, area=6×1=6  maxArea=6
  2 < heights[2]=5
  pop 2: height=5, left=1(stack top)→ width=4-1-1=2, area=5×2=10 maxArea=10
  2>heights[1]=1 → stop
  push 4                         stack=[1,4]
i=5, h=3: 3>2 → push 5           stack=[1,4,5]
i=6, h=0 (sentinel):
  0 < heights[5]=3
  pop 5: height=3, left=4→ width=6-4-1=1, area=3×1=3
  0 < heights[4]=2
  pop 4: height=2, left=1→ width=6-1-1=4, area=2×4=8
  0 < heights[1]=1
  pop 1: height=1, stack empty→ width=6,  area=1×6=6

maxArea=10 ✓

The rectangle of height 5, width 2 (indices 2-3) gives area 10.
Width formula: when stack is non-empty, the left boundary is
  i - stack.top() - 1 (distance between right edge and last shorter bar).

Problem 5: Trapping Rain Water

Problem: Given an elevation map, compute how much water can be trapped after raining.

Monotonic stack insight: Water is trapped between two taller bars. When a bar taller than the stack top arrives, we found the right boundary. The new stack top after popping provides the left boundary. The trapped water height is min(left, right) - bottom.

Output:
6
9
7
6

Dry Run: [0, 1, 0, 2, 1, 0, 1, 3, ...] → First 4 elements [0,1,0,2]

height=[0,1,0,2], water=0, stack=[]

i=0, h=0: push 0         stack=[0]
i=1, h=1: 1>height[0]=0
  bottom=0, pop 0 → stack empty → break
  push 1                 stack=[1]
i=2, h=0: 0≤height[1]=1 → push 2  stack=[1,2]
i=3, h=2: 2>height[2]=0
  bottom=2, pop 2 → left=1(stack top)
  h_water = min(height[1]=1, height[3]=2) - height[2]=0 = 1-0 = 1
  width   = 3 - 1 - 1 = 1
  water  += 1×1 = 1    water=1
  2>height[1]=1
  bottom=1, pop 1 → stack empty → break
  push 3                 stack=[3]

Total water for [0,1,0,2] = 1 unit
(the valley at index 2 traps 1 unit between bars at indices 1 and 3)

The Monotonic Stack Template

All monotonic stack problems follow the same template. The only differences are: what is stored (indices or values), what condition triggers a pop, and what computation happens at pop time.

MONOTONIC DECREASING STACK template:
  stack = []
  result = [default] * n

  for i in range(n):
      while stack and arr[stack[-1]] < arr[i]:   ← pop when current is GREATER
          idx = stack.pop()
          result[idx] = COMPUTE(arr[idx], arr[i], i, idx, stack)
      stack.append(i)

  # Elements remaining in stack: no greater element found to the right

Problems:
  Next Greater Element:  COMPUTE = arr[i]
  Daily Temperatures:    COMPUTE = i - idx
  Stock Span:           COMPUTE = i - stack[-1] if stack else i + 1

MONOTONIC INCREASING STACK template:
  stack = []
  result = [default] * n

  for i in range(n):
      while stack and arr[stack[-1]] > arr[i]:   ← pop when current is SMALLER
          idx = stack.pop()
          result[idx] = COMPUTE(arr[idx], arr[i], i, idx, stack)
      stack.append(i)

Problems:
  Next Smaller Element:      COMPUTE = arr[i]
  Previous Smaller Element:  pop before push, result = stack[-1] if stack else -1
  Largest Rectangle:         COMPUTE = height * width (requires both boundaries)
  Trapping Rain Water:       COMPUTE = min(left, right) heights × width

Problem Comparison Table

Time and Space Complexity

The O(n) proof is identical for all variants: across the entire traversal, the total number of push operations is exactly n (each element pushed exactly once). The total number of pop operations is at most n (each element popped at most once). Therefore total work is O(n) regardless of the input pattern.

Common Mistakes

Using values instead of indices in the stack. Almost every monotonic stack problem requires the index, not the value. The index is needed to compute widths, distances, and to look up the value when needed. Storing values prevents width computation in histogram and rain water problems.

Forgetting the sentinel value in largest rectangle. Without appending a 0 (or processing i = n with height 0), bars that were never popped during the loop — those that stay in the stack until the end — never get their area computed. The sentinel forces all remaining bars to be popped and computed.

Using <= vs < in the pop condition. For next greater element, pop when arr[i] > arr[top] (strictly greater). For stock span, pop when price[i] >= price[top] (greater or equal — days with equal prices are included in the span). Getting this wrong gives off-by-one errors in span calculations or misses equal-height bars.

Not handling the empty stack case when computing width. In largest rectangle, if the stack is empty after popping, the rectangle extends all the way to index 0 — width is i (the full width so far). If the stack is non-empty, width is i - stack.top() - 1 (distance between the current bar and the left boundary exclusive). Using i - stack.top() without the -1 gives width one bar too wide.

Interview Questions

Q: How do monotonic stacks achieve O(n) when there is a while loop inside the for loop?

Each element is pushed onto the stack exactly once and popped at most once. The inner while loop may run multiple iterations for a single outer loop step, but those iterations are "paid for" by previous push operations. Across the entire traversal, the total number of pop operations is bounded by the total number of push operations, which is exactly n. This amortised argument makes the total work O(n) regardless of input distribution.

Q: When would you choose the monotonic stack approach over the two-pointer approach for trapping rain water?

The two-pointer approach uses O(1) space — only four integer variables. The monotonic stack approach uses O(n) space. For production code where space is critical, use two pointers. In an interview, the monotonic stack is worth knowing because it generalises: the same code structure with minor modifications solves next greater element, daily temperatures, and stock span. The two-pointer approach is specific to rain water. If the interviewer asks for a stack-based solution, or asks you to generalise, use the monotonic stack.

Q: What is the difference between a monotonic increasing and monotonic decreasing stack?

Monotonic decreasing: each element is ≤ the element below it. An element is popped when a larger (or equal) element arrives. The pop event captures "current element is greater than popped element" — useful for next greater element problems. Monotonic increasing: each element is ≥ the element below it. An element is popped when a smaller element arrives. The pop event captures "current element is smaller than popped element" — useful for next smaller element, and computing left/right boundaries for histogram problems.

FAQs

Can a monotonic stack store values instead of indices?

Yes, for simple problems where you only need the value at pop time and not the position. Next greater element on two separate arrays (where you map values) stores values. But for most problems — daily temperatures (need index difference), largest rectangle (need width between indices), trapping rain water (need width) — you must store indices. Defaulting to storing indices is the safer choice.

Is the stack always strictly monotonic or can it have equal elements?

It depends on the problem. For next greater (strictly greater), pop when arr[i] > arr[top] — equal elements stay on the stack. For stock span (greater or equal), pop when price[i] >= price[top] — equal elements are removed. For largest rectangle, pop when height[i] < height[top] — equal heights stay, which means equal-height bars may compute slightly different widths but the maximum area is still found correctly.

What is the space complexity of the monotonic stack when the input is sorted?

For a sorted decreasing input (5, 4, 3, 2, 1), no element is ever popped during the forward pass — the stack grows to hold all n elements. Space: O(n). For a sorted increasing input (1, 2, 3, 4, 5), every previous element is popped when the next arrives — the stack holds at most 1 element at a time. Space: O(1) in the best case. The worst case space is always O(n).

Quick Quiz

Question 1: For nextGreater([3, 1, 4, 1, 5]), what is the result at index 0?

• ›A) -1
• ›B) 1
• ›C) 4
• ›D) 5

Answer: C) 4. The next element greater than 3 to its right is 4 (at index 2). When i=2 and nums[2]=4, the while loop pops index 0 (value 3) and records result[0]=4.

Question 2: In the largest rectangle histogram algorithm, what does the formula i - stack.peek() - 1 compute?

• ›A) The height of the rectangle
• ›B) The number of bars removed so far
• ›C) The width of the rectangle — distance from right edge to the left boundary (exclusive)
• ›D) The index of the tallest remaining bar

Answer: C) Width — from right boundary to left boundary. After popping the current bar, stack.peek() is the index of the last bar that is shorter than the popped bar (the left boundary). The width of the rectangle formed by the popped bar extends from stack.peek() + 1 to i - 1, which has width i - stack.peek() - 1.

Question 3: In trapping rain water, after popping the bottom bar, what do you need from the stack to compute trapped water?

• ›A) The size of the stack
• ›B) The index of the element that was pushed before bottom (the left wall)
• ›C) The maximum element in the stack
• ›D) Nothing — the computation uses only the current bar and the bottom

Answer: B) The left wall — the new stack top after popping bottom. Trapped water requires three elements: the left wall (stack.peek() after popping), the right wall (height[i], the current bar), and the bottom (height[bottom], just popped). Water height = min(height[left], height[right]) - height[bottom]. Width = i - left - 1.

Question 4: For daily temperatures [90, 80, 70] (decreasing), what does the stack contain at the end?

• ›A) Empty — all temperatures were resolved
• ›B) [0] — only index 0 (90°) remains
• ›C) [0, 1, 2] — all indices remain (no warmer day for any)
• ›D) [2] — only the last index remains

Answer: C) [0, 1, 2] — all indices remain. Since temperatures are strictly decreasing, no element is ever greater than the previous one. No pop occurs during the traversal — all three indices are pushed and none are popped. All results stay 0 (no warmer day). This is the worst case for stack space: O(n) elements simultaneously.

Summary

The monotonic stack solves a family of problems where you need to find, for each element, the nearest element to its left or right that satisfies a size condition. All variants share one performance guarantee: O(n) time because each element is pushed exactly once and popped at most once.

The five core problems:

• ›Next Greater Element — decreasing stack of indices, pop when arr[i] > arr[top], record arr[i]
• ›Daily Temperatures — decreasing stack of indices, pop when temp[i] > temp[top], record i - top
• ›Stock Span — decreasing stack of indices, pop when price[i] >= price[top], span = i - new_top or i + 1
• ›Largest Rectangle — increasing stack of indices, sentinel 0 at end, width = i - stack.top() - 1, empty stack → width = i
• ›Trapping Rain Water — decreasing stack, three elements needed: bottom (popped), left wall (new top), right wall (current i)

Template principle: decide increasing or decreasing based on whether you need "next greater" or "next smaller." Store indices (not values) unless the problem only needs the value itself. The answer computation happens at pop time — that is the moment the relationship between two elements is established.