Monotonic Stack - Complete Interview Guide

Overview

The Monotonic Stack is a powerful pattern that solves a specific class of problems: finding the next greater/smaller element for each position in an array. It’s a favorite topic in interviews because it transforms $O(n^2)$ brute force solutions into elegant $O(n)$ algorithms.

Why Interviewers Love Monotonic Stack

Tests pattern recognition - Knowing when to apply this technique is key
Requires careful thinking - Deciding between increasing vs decreasing stack
Gateway to harder problems - Histogram and rain water are classic hard problems
Efficient and elegant - Shows you can optimize beyond brute force

What is Monotonic Stack?

A monotonic stack maintains elements in either strictly increasing or strictly decreasing order. When a new element violates this order, we pop elements until the order is restored.

Visual Intuition

Monotonic DECREASING Stack (for Next Greater):

Array: [2, 1, 5, 6, 2, 3]

Step 1: Process 2
        Stack: [2]
        
Step 2: Process 1
        1 < 2, so push
        Stack: [2, 1]
        
Step 3: Process 5
        5 > 1, pop 1 → next greater of 1 is 5
        5 > 2, pop 2 → next greater of 2 is 5
        Stack: [5]
        
Step 4: Process 6
        6 > 5, pop 5 → next greater of 5 is 6
        Stack: [6]
        
Step 5: Process 2
        2 < 6, push
        Stack: [6, 2]
        
Step 6: Process 3
        3 > 2, pop 2 → next greater of 2 is 3
        3 < 6, push
        Stack: [6, 3]

Remaining in stack: 6 and 3 have no next greater element

Key Insight

Each element is pushed and popped at most once, giving us $O(n)$ time complexity.

Two Core Patterns

Pattern 1: Next Greater Element (Monotonic Decreasing)

When you need to find the next greater element, use a monotonic decreasing stack.

Pop when: current > stack.top()
Result: Elements in stack find current as their next greater

Pattern 2: Next Smaller Element (Monotonic Increasing)

When you need to find the next smaller element, use a monotonic increasing stack.

Pop when: current < stack.top()
Result: Elements in stack find current as their next smaller

Quick Reference Table

Problem Type	Stack Type	Pop Condition	What We Find
Next Greater	Decreasing	`current > top`	Next greater to right
Next Smaller	Increasing	`current < top`	Next smaller to right
Previous Greater	Decreasing	`current >= top`	Previous greater to left
Previous Smaller	Increasing	`current <= top`	Previous smaller to left

Problem 1: Next Greater Element I (LC 496)

Problem Statement

You have two integer arrays nums1 and nums2 where nums1 is a subset of nums2. For each element in nums1, find the next greater element in nums2. Return -1 if no such element exists.

Example:

nums1 = [4,1,2], nums2 = [1,3,4,2]
Output: [-1,3,-1]
Explanation: 4 has no next greater, 1’s next greater is 3, 2 has no next greater

Two Approaches

This problem can be solved with two different traversal directions, each with its own intuition:

Approach	Direction	Stack Stores	Key Insight
Left → Right	Forward	Elements waiting for answer	Current element is the “answer” for smaller stack elements
Right → Left	Backward	Candidates for next greater	Stack top is the answer for current element

Approach 1: Left to Right (Forward Traversal)

Intuition: Traverse from left to right. When we encounter an element, it becomes the “next greater” for all smaller elements waiting in the stack.

Array: [1, 3, 4, 2]

i=0: Process 1, stack empty → push 1
     Stack: [1]
     
i=1: Process 3, 3 > 1 → pop 1, record nextGreater[1] = 3
     Push 3
     Stack: [3]
     
i=2: Process 4, 4 > 3 → pop 3, record nextGreater[3] = 4
     Push 4
     Stack: [4]
     
i=3: Process 2, 2 < 4 → push 2
     Stack: [4, 2]

Result: 4 and 2 have no next greater (remain in stack)

Try it yourself (Left → Right):

Initializing...

Approach 2: Right to Left (Backward Traversal)

Intuition: Traverse from right to left. The stack maintains “candidates” for being the next greater element. Stack top (if exists and greater) is the answer.

Array: [1, 3, 4, 2]

i=3: Process 2, stack empty → nextGreater[2] = -1, push 2
     Stack: [2]
     
i=2: Process 4, 4 > 2 → pop 2 (can't be answer for anyone)
     Stack empty → nextGreater[4] = -1, push 4
     Stack: [4]
     
i=1: Process 3, 3 < 4 → nextGreater[3] = 4, push 3
     Stack: [4, 3]
     
i=0: Process 1, 1 < 3 → nextGreater[1] = 3, push 1
     Stack: [4, 3, 1]

Result: Same answer, different thought process!

Try it yourself (Right → Left):

Initializing...

Comparison

Aspect	Left → Right	Right → Left
When answer is found	When we find a larger element	Immediately for current element
Stack role	”Waiting room” for unanswered	”Candidate pool” for answers
Mental model	”Who does this element help?"	"Who can help this element?”
Pop condition	`stack.top() < current`	`stack.top() <= current`

Both approaches have the same time and space complexity. Choose based on which intuition feels more natural to you!

Complexity Analysis

Time: $O(n + m)$ where n = len(nums1), m = len(nums2)
Space: $O(m)$ for the hash map and stack

Problem 2: Next Greater Element II (LC 503)

Problem Statement

Given a circular array, find the next greater element for each position. The array wraps around, so after the last element comes the first.

Example:

Input: [1,2,1]
Output: [2,-1,2]
Explanation: Element at index 2 (value 1) wraps around and finds 2 at index 1

Intuition

Trick: Process the array twice to simulate circular behavior.

Array: [1, 2, 1]
Process: [1, 2, 1, 1, 2, 1]  (virtual concatenation)
                  ↑ only use first pass for pushing indices

Solution

Why Process Twice?

First pass: Build partial results, push all indices to stack
Second pass: Elements remaining in stack get a chance to find their next greater

Complexity Analysis

Time: $O(n)$ - each element processed at most twice
Space: $O(n)$ - stack can hold all indices

Problem 3: Daily Temperatures (LC 739)

Problem Statement

Given daily temperatures, return how many days you have to wait for a warmer temperature. If there is no warmer day, return 0.

Example:

Input: [73,74,75,71,69,72,76,73]
Output: [1,1,4,2,1,1,0,0]

Intuition

This is “Next Greater Element” where we return the distance instead of the value.

Day 0 (73°): Next warmer is day 1 (74°) → wait 1 day
Day 2 (75°): Next warmer is day 6 (76°) → wait 4 days

Solution

Interactive Visualization

Initializing...

Key Difference from Next Greater Element

Store indices in stack (not values)
Result is currentIndex - poppedIndex

Complexity Analysis

Time: $O(n)$
Space: $O(n)$

Problem 4: Largest Rectangle in Histogram (LC 84)

Problem Statement

Given an array of heights representing a histogram, find the area of the largest rectangle.

     ██
  ██ ██
  ██ ██ ██
██ ██ ██ ██
heights = [2,1,5,6,2,3]
Answer = 10 (rectangle of height 5, width 2)

Intuition

For each bar, we want to know:

How far left it can extend (until a shorter bar)
How far right it can extend (until a shorter bar)

The monotonic stack finds both efficiently by tracking when a bar can no longer extend.

Key Insight

When we pop a bar (because current bar is shorter), we know:

Right boundary: current index
Left boundary: top of stack after pop
Height: the popped bar’s height

Pop bar at index i when heights[i] > current:
  width = current_index - stack_top - 1
  area = height[i] * width

Solution

Walkthrough Example

heights = [2, 1, 5, 6, 2, 3, 0(sentinel)]

i=0: push 0, stack=[0]
i=1: 1 < 2, pop 0, area=2*1=2, push 1, stack=[1]
i=2: push 2, stack=[1,2]
i=3: push 3, stack=[1,2,3]
i=4: 2 < 6, pop 3, area=6*1=6
     2 < 5, pop 2, area=5*2=10
     push 4, stack=[1,4]
i=5: push 5, stack=[1,4,5]
i=6: 0 < all, pop 5, area=3*1=3
     pop 4, area=2*4=8
     pop 1, area=1*6=6

Max area = 10

Complexity Analysis

Time: $O(n)$
Space: $O(n)$

📖 For more detailed solutions, see Largest Rectangle in Histogram - Three Solutions with Interactive Visualization.

Problem 5: Trapping Rain Water (LC 42)

Problem Statement

Given elevation map after rain, calculate how much water can be trapped.

Input: [0,1,0,2,1,0,1,3,2,1,2,1]
Output: 6 (units of trapped water)

Intuition

Water is trapped in “valleys” between bars. For each valley:

Left wall: previous taller bar
Right wall: current bar (taller than valley bottom)
Water height: min(left, right) - valley bottom

Stack Approach

Maintain a monotonic decreasing stack. When we find a bar taller than stack top:

Pop the bottom of the valley
Calculate water trapped using left wall (new stack top), right wall (current), and bottom

Solution

Walkthrough Example

height = [0, 1, 0, 2, 1, 0, 1, 3]

i=0: push 0, stack=[0]
i=1: 1 > 0, pop 0, stack empty, no water
     push 1, stack=[1]
i=2: 0 < 1, push 2, stack=[1,2]
i=3: 2 > 0, pop 2 (bottom)
     left=1, right=3, h=min(1,2)-0=1, w=1
     water += 1*1 = 1
     push 3, stack=[1,3]
...continue for remaining elements

Alternative: Two Pointers

There’s also a two-pointer approach with O(1) space:

def trap(self, height):
    left, right = 0, len(height) - 1
    left_max, right_max = 0, 0
    water = 0
    
    while left < right:
        if height[left] < height[right]:
            if height[left] >= left_max:
                left_max = height[left]
            else:
                water += left_max - height[left]
            left += 1
        else:
            if height[right] >= right_max:
                right_max = height[right]
            else:
                water += right_max - height[right]
            right -= 1
    
    return water

Complexity Analysis

Stack approach:

Time: $O(n)$
Space: $O(n)$

Two pointers:

Time: $O(n)$
Space: $O(1)$

Templates & Patterns

Template 1: Next Greater Element

def nextGreater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # indices
    
    for i in range(n):
        while stack and nums[stack[-1]] < nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    
    return result

Template 2: Next Smaller Element

def nextSmaller(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # indices
    
    for i in range(n):
        while stack and nums[stack[-1]] > nums[i]:
            result[stack.pop()] = nums[i]
        stack.append(i)
    
    return result

Template 3: Circular Array

def nextGreaterCircular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    
    for i in range(2 * n):  # Process twice
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)
    
    return result

Template 4: Histogram/Area Problems

def histogramPattern(heights):
    stack = []
    result = 0
    
    for i, h in enumerate(heights + [0]):  # Sentinel
        while stack and heights[stack[-1]] > h:
            popped = stack.pop()
            width = i if not stack else i - stack[-1] - 1
            result = max(result, heights[popped] * width)
        stack.append(i)
    
    return result

Complexity Analysis

Problem	Time	Space
Next Greater Element I	O(n+m)	O(n)
Next Greater Element II	O(n)	O(n)
Daily Temperatures	O(n)	O(n)
Largest Rectangle in Histogram	O(n)	O(n)
Trapping Rain Water (stack)	O(n)	O(n)
Trapping Rain Water (two ptr)	O(n)	O(1)

Why O(n)?

Each element is pushed at most once and popped at most once. Even though we have a while loop inside the for loop, the total number of operations is bounded by 2n.

Interview Tips

Pattern Recognition

Ask yourself these questions:

“Am I looking for the next greater/smaller element?”
“Do I need distances or values?”
“Is the array circular?”
“Am I calculating areas or trapped volumes?”

Common Mistakes

Wrong stack type: Using increasing when you need decreasing (or vice versa)
Forgetting indices: For problems needing distances, store indices not values
Circular array: Remember to process twice but only push in first pass
Sentinel values: Forgetting to add a 0 at the end for histogram problems

Follow-up Questions

“Can you do it with O(1) space?” (Trapping Rain Water → two pointers)
“What if there are duplicates?” → Use <= instead of < when needed
“What about 2D histograms?” → Apply 1D histogram per row (LC 85)

How to Explain

State the pattern: “This is a next greater element problem”
Explain stack type: “I’ll use a monotonic decreasing stack because…”
Walk through example: Show push/pop operations on small input
Analyze complexity: “Each element is pushed/popped once, so O(n)“

Summary

Key takeaways for monotonic stack:

Two patterns: Decreasing stack for next greater, increasing for next smaller
Store indices: When you need distances or positions
Circular arrays: Process twice, push only in first pass
Histogram problems: Use sentinel values (0) to trigger final pops
O(n) guarantee: Each element pushed and popped at most once

Master these patterns, and you’ll recognize monotonic stack problems instantly in interviews!