Monotonic Stack and Deque: The Pattern Behind 15 Hard Interview Problems

A monotonic stack is just a stack that maintains a sorted order — either always increasing or always decreasing. That constraint makes it surprisingly powerful: it lets you find the next greater element, the nearest smaller element, or the largest rectangle — all in O(n).

The pattern appears in at least 15 medium-hard problems on LeetCode and regularly shows up at product company interviews. Most students either memorise the specific solutions or avoid these problems entirely. This guide teaches the underlying pattern so you can derive any variant yourself.

---

The Core Idea

A monotonic stack processes elements one by one and maintains an invariant: every element in the stack is either all increasing or all decreasing from bottom to top.

When a new element violates the invariant, you pop elements until the invariant holds again. The moment of popping is information — it tells you something about the relationship between the popped element and the new element.

Monotonic decreasing stack rule: Pop elements that are smaller than the current element.

Monotonic increasing stack rule: Pop elements that are larger than the current element.

---

Pattern 1: Next Greater Element

Problem: For each element, find the first element to the right that is greater than it. Return -1 if none exists.

def next_greater(nums):
    n = len(nums)
    result = [-1] * n
    stack = []  # stores indices of elements awaiting their "next greater"
    
    for i in range(n):
        # Pop elements smaller than current — current is their next greater
        while stack and nums[stack[-1]] < nums[i]:
            idx = stack.pop()
            result[idx] = nums[i]
        stack.append(i)
    
    # Remaining elements in stack have no next greater (stay -1)
    return result

# nums = [4, 1, 2, 3]
# i=0: stack=[0] (4 has no greater seen yet)
# i=1: 1 < 4, stack=[0,1]
# i=2: 2 > 1 → pop 1, result[1]=2. 2 < 4, stack=[0,2]
# i=3: 3 > 2 → pop 2, result[2]=3. 3 < 4, stack=[0,3]
# Remaining: result[0]=result[3]=-1
# Output: [-1, 2, 3, -1] ✓

Why it's O(n): Each element is pushed once and popped once. Total operations = 2n.

Circular Next Greater Element

For a circular array (after the last element, wrap to the first):

def next_greater_circular(nums):
    n = len(nums)
    result = [-1] * n
    stack = []
    
    # Iterate twice to simulate circular behavior
    for i in range(2 * n):
        idx = i % n
        while stack and nums[stack[-1]] < nums[idx]:
            result[stack.pop()] = nums[idx]
        if i < n:
            stack.append(idx)
    
    return result

---

Pattern 2: Daily Temperatures (Next Greater With Distance)

Problem: Given temperatures, find for each day how many days until a warmer day.

def daily_temperatures(temperatures):
    n = len(temperatures)
    result = [0] * n
    stack = []  # indices
    
    for i in range(n):
        while stack and temperatures[stack[-1]] < temperatures[i]:
            idx = stack.pop()
            result[idx] = i - idx   # distance to next warmer day
        stack.append(i)
    
    return result

The only change from "next greater": instead of storing the value, store the distance (i - idx).

---

Pattern 3: Largest Rectangle in Histogram

Problem: Given bar heights, find the area of the largest rectangle you can form.

This is the canonical "hard" monotonic stack problem. Understanding it unlocks a dozen variants.

Key insight: For each bar, the maximum rectangle with that bar as the shortest is determined by the nearest shorter bar on each side. A monotonic increasing stack gives us exactly this.

def largest_rectangle(heights):
    heights.append(0)  # sentinel: forces all remaining bars to be processed
    stack = []         # monotonic increasing stack of indices
    max_area = 0
    
    for i, h in enumerate(heights):
        start = i
        
        while stack and heights[stack[-1]] > h:
            idx = stack.pop()
            width = i - stack[-1] - 1 if stack else i
            max_area = max(max_area, heights[idx] * width)
            start = idx  # the popped bar can extend left to here
        
        stack.append(i)
    
    heights.pop()  # restore original
    return max_area

Trace for [2, 1, 5, 6, 2, 3]:

i=0, h=2: stack=[0]
i=1, h=1: pop 0 (height 2), width=1, area=2. stack=[1]
i=2, h=5: stack=[1,2]
i=3, h=6: stack=[1,2,3]
i=4, h=2: pop 3 (h=6), w=4-2-1=1, area=6. pop 2 (h=5), w=4-1-1=2, area=10. stack=[1,4]
i=5, h=3: stack=[1,4,5]
i=6, h=0: pop 5 (h=3), w=6-4-1=1, area=3. pop 4 (h=2), w=6-1-1=4, area=8. pop 1 (h=1), w=6, area=6.
max_area = 10 ✓

Maximal Rectangle in Binary Matrix

Problem: Find the largest rectangle containing only 1s in a binary matrix.

This reduces to "largest rectangle in histogram" applied row by row:

def maximal_rectangle(matrix):
    if not matrix:
        return 0
    
    cols = len(matrix[0])
    heights = [0] * cols
    max_area = 0
    
    for row in matrix:
        # Update histogram heights
        for j in range(cols):
            heights[j] = heights[j] + 1 if row[j] == '1' else 0
        
        max_area = max(max_area, largest_rectangle(heights))
    
    return max_area

---

Pattern 4: Trapping Rain Water (Stack Approach)

We covered this with two pointers in another article. Here's the stack solution, which generalises more easily:

def trap_rain_water(height):
    stack = []
    water = 0
    
    for i, h in enumerate(height):
        while stack and height[stack[-1]] < h:
            bottom = stack.pop()
            if not stack:
                break
            width = i - stack[-1] - 1
            bounded_height = min(height[stack[-1]], h) - height[bottom]
            water += width * bounded_height
        stack.append(i)
    
    return water

---

Pattern 5: Sum of Subarray Minimums

Problem: Find the sum of min(subarray) for every contiguous subarray. Return result mod 10^9 + 7.

Key insight: For each element, count how many subarrays it is the minimum of. Use the monotonic stack to find the "previous smaller" and "next smaller" boundaries.

def sum_subarray_mins(arr):
    MOD = 10**9 + 7
    n = len(arr)
    
    # For each element, find:
    # left[i] = distance to previous smaller element (or beginning)
    # right[i] = distance to next smaller or equal element (or end)
    
    left = [0] * n
    right = [0] * n
    stack = []
    
    # Previous smaller
    for i in range(n):
        while stack and arr[stack[-1]] >= arr[i]:
            stack.pop()
        left[i] = i - stack[-1] if stack else i + 1
        stack.append(i)
    
    stack = []
    # Next smaller or equal (use <= to avoid double-counting)
    for i in range(n - 1, -1, -1):
        while stack and arr[stack[-1]] > arr[i]:
            stack.pop()
        right[i] = stack[-1] - i if stack else n - i
        stack.append(i)
    
    result = 0
    for i in range(n):
        result += arr[i] * left[i] * right[i]
    
    return result % MOD

left[i] * right[i] = number of subarrays where arr[i] is the minimum.

---

Pattern 6: Monotonic Deque (Sliding Window Maximum)

The deque variant maintains a monotonic decreasing queue. The front always holds the maximum of the current window.

from collections import deque

def sliding_window_max(nums, k):
    dq = deque()  # stores indices; values are decreasing front-to-back
    result = []
    
    for i in range(len(nums)):
        # Remove indices outside the window
        while dq and dq[0] <= i - k:
            dq.popleft()
        
        # Maintain decreasing order: remove smaller values from back
        while dq and nums[dq[-1]] < nums[i]:
            dq.pop()
        
        dq.append(i)
        
        # Window is fully formed
        if i >= k - 1:
            result.append(nums[dq[0]])
    
    return result

Why deque and not stack? We need to remove from both ends: old elements expire from the front (leaving the window), smaller elements are evicted from the back (maintaining order).

---

Which Variant to Use?

| Problem asks for | Stack type | Pop condition | |---|---|---| | Next greater element | Monotonic decreasing | Current > stack top | | Next smaller element | Monotonic increasing | Current < stack top | | Previous greater (to the left) | Monotonic decreasing | Process right-to-left | | Maximum in sliding window | Monotonic decreasing deque | Remove smaller from back | | Minimum in sliding window | Monotonic increasing deque | Remove larger from back | | Largest rectangle / rain water | Monotonic increasing | Current < stack top |

---

The General Template

stack = []  # usually stores indices

for i, val in enumerate(array):
    while stack and CONDITION(array[stack[-1]], val):
        popped = stack.pop()
        # --- This is where you compute your answer ---
        # You now know: popped's "next" that satisfied CONDITION is val
        # The element to popped's "left boundary" is stack[-1] (if exists)
        # ----------------------------------------------
    stack.append(i)

Fill in CONDITION based on what you need:

• Next greater → array[stack[-1]] < val
• Next smaller → array[stack[-1]] > val
• Largest rectangle → array[stack[-1]] > val (process on pop, calculate width)

Start here: Solve Daily Temperatures, then Next Greater Element II (circular), then Largest Rectangle in Histogram — in that order. Each one teaches the next piece. Use the AI Tutor if you get stuck on the rectangle problem's width calculation.