Stacks & QueuesTemplate 1 of 2

Stack & QueueIntermediateO(n) time, O(n) space

Monotonic Stack

The Intuition

A monotonic stack is a stack that maintains a strict ordering on its contents (always increasing or always decreasing from bottom to top). The invariant is enforced on every push: before pushing a new element, pop all elements that violate the order. This pattern computes "next greater" or "next smaller" element relations in O(n) total time despite the inner pop loop, because every element is pushed and popped at most once across the entire scan.

The canonical use is Next Greater Element. Iterate left to right. Maintain a stack of indices whose answers are not yet known, kept in strictly decreasing order of value. When a new element nums[i] is larger than the value at the top index, pop the top: the popped index's answer is nums[i], since nums[i] is the first element to its right that exceeds it. Continue popping until the stack is empty or the top is at least nums[i], then push i. After the scan, any indices left on the stack have no greater element to their right.

The mirror version uses an increasing stack to compute next smaller element. Iterating right to left instead of left to right computes the previous greater (or previous smaller) variants. The four combinations cover most NGE/NSE problems.

Two harder applications reuse the same skeleton:

Largest Rectangle in Histogram (LC 84). Maintain a stack of indices whose heights are increasing. When a shorter bar arrives, pop the top: the popped bar's max rectangle has height = popped value, left boundary = new top of stack + 1, right boundary = current index - 1. Push a sentinel zero at the end to flush the stack.
Trapping Rain Water (LC 42). Decreasing stack of bar indices. When a higher bar arrives, pop the top: the trapped water above the popped bar is bounded by min(left wall, right wall) - popped height, multiplied by the gap width. Useful as an alternative to the two-pointer solution.

The trick to recognizing this pattern is the phrase "next/previous greater/smaller" in the problem, or any time you find yourself wanting to scan rightward from each element.

When to use

Next greater/smaller element, largest rectangle in histogram, trapping rain water, stock span, daily temperatures, or any problem requiring efficient comparison with "nearby" elements.

When NOT to use

Need the K-th greater element (use heap)
Sliding window min/max (use monotonic queue)
Need both next greater AND next smaller simultaneously

Pattern Recognition

next greater / next smaller elementprevious greater / previous smaller elementlargest rectangle in a histogramtrapping rain water or stock spandaily temperatures or any how many days until...

Edge Cases

all increasing
all decreasing
single element

Practice Problems

EasyNext Greater Element I

MediumDaily Temperatures

HardLargest Rectangle in Histogram

HardTrapping Rain Water

Key Points

•Maintain a stack in strictly increasing or decreasing order
•Pop elements that violate the monotonic property
•Each element is pushed and popped at most once. Total O(n)
•Useful for finding next greater/smaller element
•Can store indices instead of values for more information

Code Template

def next_greater_element(arr):
    """For each element, find the next greater element to its right."""
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices

    for i in range(n):
        while stack and arr[i] > arr[stack[-1]]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)

    return result

def largest_rectangle_histogram(heights):
    """Find largest rectangle in histogram."""
    stack = []
    max_area = 0
    heights.append(0)  # sentinel

    for i, h in enumerate(heights):
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            max_area = max(max_area, height * width)
        stack.append(i)

    heights.pop()  # remove sentinel
    return max_area

func nextGreaterElement(arr []int) []int {
    // For each element, find the next greater element to its right.
    n := len(arr)
    result := make([]int, n)
    for i := range result {
        result[i] = -1
    }
    stack := []int{} // stores indices

    for i := 0; i < n; i++ {
        for len(stack) > 0 && arr[i] > arr[stack[len(stack)-1]] {
            idx := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            result[idx] = arr[i]
        }
        stack = append(stack, i)
    }
    return result
}

func largestRectangleHistogram(heights []int) int {
    // Find largest rectangle in histogram.
    stack := []int{}
    maxArea := 0
    heights = append(heights, 0) // sentinel

    for i, h := range heights {
        for len(stack) > 0 && heights[stack[len(stack)-1]] > h {
            top := stack[len(stack)-1]
            stack = stack[:len(stack)-1]
            height := heights[top]
            width := i
            if len(stack) > 0 {
                width = i - stack[len(stack)-1] - 1
            }
            if height*width > maxArea {
                maxArea = height * width
            }
        }
        stack = append(stack, i)
    }
    return maxArea
}

public int[] nextGreaterElement(int[] arr) {
    // For each element, find the next greater element.
    int n = arr.length;
    int[] result = new int[n];
    Arrays.fill(result, -1);
    Deque<Integer> stack = new ArrayDeque<>();

    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty()
                && arr[i] > arr[stack.peek()]) {
            result[stack.pop()] = arr[i];
        }
        stack.push(i);
    }
    return result;
}

public int largestRectangleHistogram(int[] heights) {
    // Find largest rectangle in histogram.
    Deque<Integer> stack = new ArrayDeque<>();
    int maxArea = 0;
    int n = heights.length;

    for (int i = 0; i <= n; i++) {
        int h = (i == n) ? 0 : heights[i];
        while (!stack.isEmpty()
                && heights[stack.peek()] > h) {
            int height = heights[stack.pop()];
            int width = stack.isEmpty()
                        ? i : i - stack.peek() - 1;
            maxArea = Math.max(maxArea, height * width);
        }
        stack.push(i);
    }
    return maxArea;
}

Common Mistakes

Confusing when to use increasing vs decreasing stack
Not handling remaining elements in the stack after iteration
Using values instead of indices when position information is needed

Related Patterns

CrackingWalnuts