Monotonic Stack & Queue

Back to DSA & Algorithms/00 - Roadmap Overview

What is a Monotonic Stack?

A monotonic stack is a stack where elements are always in sorted order (either increasing or decreasing). When a new element would violate the order, we pop elements until the order is restored.

The Mental Model

Imagine you're stacking books on a shelf by height, and you have a rule: each book must be shorter than the one below it (decreasing stack). When a tall book arrives, you remove all shorter books that are now "overshadowed."

Why It's Useful

It solves "next greater/smaller element" problems in O(n), which would otherwise be O(n²). The stack stores elements that are "waiting" for their answer. When we find their answer (a greater/smaller element), we pop them.

Pattern 1: Next Greater Element

Decreasing monotonic stack. When a bigger element comes, all smaller elements on the stack have found their "next greater."

java
public int[] nextGreaterElement(int[] nums) {
    int n = nums.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();  // Stores INDICES, values in DECREASING order

    for (int i = 0; i < n; i++) {
        // Current element is greater than stack top?
        // → Stack top has found its "next greater"
        while (!stack.isEmpty() && nums[i] > nums[stack.peek()]) {
            int idx = stack.pop();
            result[idx] = nums[i];
        }

        stack.push(i);
    }

    return result;
}

// Walkthrough: [2, 1, 2, 4, 3]
//
// i=0, val=2: stack empty → push 0. stack=[0]
//   Stack state: [2]
//
// i=1, val=1: 1 < 2 → push 1. stack=[0,1]
//   Stack state: [2, 1]  ← decreasing ✓
//
// i=2, val=2: 2 > 1 → pop 1, result[1]=2
//             2 = 2 (not >) → push 2. stack=[0,2]
//   Stack state: [2, 2]
//
// i=3, val=4: 4 > 2 → pop 2, result[2]=4
//             4 > 2 → pop 0, result[0]=4
//             push 3. stack=[3]
//   Stack state: [4]
//
// i=4, val=3: 3 < 4 → push 4. stack=[3,4]
//   Stack state: [4, 3]
//
// Remaining in stack: no next greater → stay -1
// Result: [4, 2, 4, -1, -1]

Which Stack Direction for Which Problem?

"Next GREATER element" → DECREASING stack (pop when current > top)
  Stack holds elements waiting for something BIGGER
  
"Next SMALLER element" → INCREASING stack (pop when current < top)
  Stack holds elements waiting for something SMALLER
  
"Previous GREATER element" → Iterate BACKWARDS with decreasing stack
"Previous SMALLER element" → Iterate BACKWARDS with increasing stack

Daily Temperatures

java
// How many days until a warmer temperature?
public int[] dailyTemperatures(int[] temperatures) {
    int n = temperatures.length;
    int[] result = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();  // Indices, temperatures decreasing

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int prev = stack.pop();
            result[prev] = i - prev;  // Days between
        }

        stack.push(i);
    }

    return result;
}

// [73, 74, 75, 71, 69, 72, 76, 73]
// → [1,  1,  4,  2,  1,  1,  0,  0]

Problems

Pattern 2: Largest Rectangle in Histogram

This is the most important monotonic stack problem. Know it cold.

For each bar, we want to know how far left and right it can extend as the shortest bar. The area = height × width.

java
public int largestRectangleArea(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();  // Indices, heights in INCREASING order
    int maxArea = 0;

    for (int i = 0; i <= heights.length; i++) {
        // Use 0 as sentinel to flush remaining bars
        int h = (i < heights.length) ? heights[i] : 0;

        while (!stack.isEmpty() && h < heights[stack.peek()]) {
            // Current bar is shorter → previous bar can't extend right
            int height = heights[stack.pop()];

            // Width = distance between current bar and new stack top
            int width = stack.isEmpty() ? i : i - stack.peek() - 1;

            maxArea = Math.max(maxArea, height * width);
        }

        stack.push(i);
    }

    return maxArea;
}

// Walkthrough: [2, 1, 5, 6, 2, 3]
//
// i=0, h=2: push. stack=[0]
// i=1, h=1: 1 < 2 → pop 0.
//   height=2, width=1 (no stack top → width=i=1). area=2
//   push 1. stack=[1]
// i=2, h=5: push. stack=[1,2]
// i=3, h=6: push. stack=[1,2,3]
// i=4, h=2: 2 < 6 → pop 3.
//   height=6, width=4-2-1=1. area=6
//   2 < 5 → pop 2.
//   height=5, width=4-1-1=2. area=10  ← max!
//   push 4. stack=[1,4]
// i=5, h=3: push. stack=[1,4,5]
// i=6 (sentinel h=0): flush remaining
//   pop 5: height=3, width=6-4-1=1. area=3
//   pop 4: height=2, width=6-1-1=4. area=8
//   pop 1: height=1, width=6 (no stack). area=6
//
// Answer: 10

// Why the width calculation works:
// When we pop index `idx`:
//   - Right boundary = current i (first shorter bar to the right)
//   - Left boundary = new stack top (first shorter bar to the left)
//   - Width = i - stack.peek() - 1
// If stack is empty, the bar extends all the way to the left edge:
//   - Width = i

Trapping Rain Water (Alternative Monotonic Stack Approach)

java
public int trap(int[] height) {
    Deque<Integer> stack = new ArrayDeque<>();
    int water = 0;

    for (int i = 0; i < height.length; i++) {
        while (!stack.isEmpty() && height[i] > height[stack.peek()]) {
            int bottom = height[stack.pop()];
            if (stack.isEmpty()) {
                break;
            }
            int left = stack.peek();
            int h = Math.min(height[left], height[i]) - bottom;
            int w = i - left - 1;
            water += h * w;
        }

        stack.push(i);
    }

    return water;
}

Problems

Pattern 3: Monotonic Deque (Sliding Window Max/Min)

What it is

A deque (double-ended queue) that maintains elements in sorted order. Supports O(1) max/min queries within a sliding window.

The Mental Model

You're looking at a landscape through a window that slides right. You want to track the tallest mountain visible. When a new, taller mountain enters the window, all shorter mountains in front of it will never be the answer again (they leave the window first AND are shorter) → remove them from the back of the deque.

java
public int[] maxSlidingWindow(int[] nums, int k) {
    Deque<Integer> dq = new ArrayDeque<>();  // Stores INDICES, values in DECREASING order
    int[] result = new int[nums.length - k + 1];
    int ri = 0;

    for (int i = 0; i < nums.length; i++) {
        // Remove indices outside the window
        while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
            dq.pollFirst();
        }

        // Remove smaller elements from back (they'll never be the max)
        while (!dq.isEmpty() && nums[i] >= nums[dq.peekLast()]) {
            dq.pollLast();
        }

        dq.addLast(i);

        // Window is full → record the maximum (front of deque)
        if (i >= k - 1) {
            result[ri++] = nums[dq.peekFirst()];
        }
    }

    return result;
}

// Walkthrough: nums=[1,3,-1,-3,5,3,6,7], k=3
//
// i=0, val=1: dq=[0]. Window not full yet.
// i=1, val=3: 3>1 → pop 0. dq=[1]. Not full yet.
// i=2, val=-1: -1<3 → append. dq=[1,2]. Full! max=nums[1]=3
// i=3, val=-3: dq[0]=1 ≥ 3-3+1=1 → keep. -3<-1 → append. dq=[1,2,3]. max=3
// i=4, val=5: dq[0]=1 < 4-3+1=2 → pollFirst. dq=[2,3].
//   5>-3 → pop 3. 5>-1 → pop 2. dq=[4]. max=5
// i=5, val=3: 3<5 → append. dq=[4,5]. max=5
// i=6, val=6: 6>3 → pop 5. 6>5 → pop 4. dq=[6]. max=6
// i=7, val=7: 7>6 → pop 6. dq=[7]. max=7
// Result: [3, 3, 5, 5, 6, 7]

Problems

Things to Be Aware Of

1. Store INDICES, Not Values

java
// Storing indices lets you:
// - Calculate distances (daily temperatures, rectangle width)
// - Check if elements are within a window (sliding window)
// - Look up the actual value via nums[idx]

2. Circular Array → Iterate 2n

java
// For circular "next greater", iterate through the array TWICE:
for (int i = 0; i < 2 * n; i++) {
    while (!stack.isEmpty() && nums[i % n] > nums[stack.peek()]) {
        result[stack.pop()] = nums[i % n];
    }
    if (i < n) {
        stack.push(i);
    }
}

3. Sentinel Values

java
// Adding a 0 at the end of heights array (histogram problem)
// forces all remaining bars to be processed.
// This eliminates the need for post-loop cleanup.

Decision Guide

"Next greater/smaller element for each position"
  └── Monotonic stack

"Largest rectangle / maximal area"
  └── Monotonic stack (increasing, histogram pattern)

"Sliding window maximum/minimum"
  └── Monotonic deque

"Trapping rain water"
  └── Two pointers (simpler) OR monotonic stack

"Circular array next greater"
  └── Monotonic stack, iterate 2n with modulo