Skip to main content
Monotonic Stack Pattern

​
What is Monotonic Stack?

Monotonic Stack maintains elements in sorted order (either increasing or decreasing). It efficiently solves “next greater/smaller” problems in O(n).

​
When to Use

Next Greater Element

Find next larger element for each position

Previous Smaller

Find previous smaller element

Histogram Problems

Largest rectangle, trapping water

Stock Span

Days since last higher price

​
Pattern Variations

​
1. Next Greater Element

def next_greater_element(nums):
    """For each element, find next greater or -1"""
    n = len(nums)
    result = [-1] * n
    stack = []  # Stores indices
    
    for i in range(n):
        while stack and nums[i] > nums[stack[-1]]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    
    return result

# Example: [2,1,2,4,3] returns [4,2,4,-1,-1]

​
2. Previous Smaller Element

def previous_smaller(nums):
    """For each element, find previous smaller or -1"""
    n = len(nums)
    result = [-1] * n
    stack = []
    
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:
            stack.pop()
        
        if stack:
            result[i] = nums[stack[-1]]
        
        stack.append(i)
    
    return result

​
3. Largest Rectangle in Histogram

def largest_rectangle_area(heights):
    """Find largest rectangle in histogram"""
    stack = []  # (index, height)
    max_area = 0
    
    for i, h in enumerate(heights):
        start = i
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()
            max_area = max(max_area, height * (i - idx))
            start = idx
        stack.append((start, h))
    
    # Process remaining
    for idx, height in stack:
        max_area = max(max_area, height * (len(heights) - idx))
    
    return max_area

​
4. Daily Temperatures

def daily_temperatures(temperatures):
    """Days until warmer temperature"""
    n = len(temperatures)
    result = [0] * n
    stack = []  # Stores indices
    
    for i in range(n):
        while stack and temperatures[i] > temperatures[stack[-1]]:
            idx = stack.pop()
            result[idx] = i - idx
        stack.append(i)
    
    return result

​
5. Trapping Rain Water

def trap(height):
    """Calculate trapped water using monotonic stack"""
    stack = []  # Stores indices
    water = 0
    
    for i, h in enumerate(height):
        while stack and h > height[stack[-1]]:
            bottom = stack.pop()
            if not stack:
                break
            
            width = i - stack[-1] - 1
            bounded_height = min(h, height[stack[-1]]) - height[bottom]
            water += width * bounded_height
        
        stack.append(i)
    
    return water

​
Classic Problems

ProblemStack TypeKey Insight
Next GreaterDecreasingPop smaller, push current
Previous SmallerIncreasingPop larger or equal
HistogramDecreasingCalculate area on pop
Daily TemperaturesDecreasingStore indices, compute diff
Stock SpanDecreasingCount days with smaller price

​
Practice Problems

Next Greater Element I

Basic monotonic stack

Largest Rectangle

Classic histogram problem

Trapping Rain Water

Multi-approach problem

Sum of Subarray Mins

Contribution technique