Monotonic Stack Pattern: LeetCode Guide & Problems

Maintain a sorted stack to find next/previous greater or smaller elements in O(n).

✓ Pattern Solutions & Guides Practice Mode Enabled

7 Problem 1 Easy 5 Medium 1 Hard

Overview

A monotonic stack keeps elements in sorted order (increasing or decreasing). It is the key insight for problems asking about next/previous greater or smaller elements, and for computing areas in histograms.

When to Use

Largest rectangle in histogram
Trapping rain water
Daily temperatures
Online stock span
Remove k digits

Common Mistakes

Not clearing remaining elements in the stack after the loop
Confusing monotonic increasing vs decreasing for the problem
Using monotonic stack for problems solvable with two pointers

Complexity

Time

O(n) — each element pushed/popped once

Space

O(n)

// Largest Rectangle in Histogram
public int largestRectangle(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    stack.push(-1);
    int maxArea = 0;

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

Problems (7)

Hide completed

Problem	Difficulty	Companies	Freq	Solution
Largest Rectangle in Histogram #Array #Stack #Monotonic Stack	Hard	AmazonGoogle +1	High	Solution
Next Greater Element I #Array #Hash Map #Stack	Easy	Apple	Medium	Solution
Sum of Subarray Minimums #Array #Dynamic Programming #Stack	Medium	GoogleAmazon	Medium	Solution
Online Stock Span #Stack #Design #Monotonic Stack	Medium	AmazonMicrosoft	Medium	Solution
132 Pattern #Array #Binary Search #Stack	Medium	GoogleAmazon +1	Medium	Solution
Remove Duplicate Letters #String #Stack #Greedy	Medium	GoogleLyft	Medium	Solution
Stock Span Problem #Stack	Medium	AmazonGoogle +1	High	Solution

🧠

Mastering the Monotonic Stack Pattern for Coding Interviews

1. Mental Model & Visual Intuition

The Monotonic Stack pattern is designed to eliminate redundant work and reduce search spaces. Rather than evaluating every possible state using a naive brute-force approach, this pattern relies on an invariant that allows you to safely discard subproblems that cannot lead to an optimal answer. When encountering an interview question, look for core triggers such as monotonicity, contiguous constraints, optimal substructure, or overlapping subproblems.

2. Algorithmic Invariants & Step-by-Step Execution

To implement this pattern flawlessly under interview conditions, structure your thought process into three discrete steps:

State Initialization: Define your boundaries, pointers, or memoization tables clearly before entering loops.
State Transition: Update tracking variables incrementally as new elements enter or leave your active evaluation window.
Feasibility Check: When constraints are violated, systematically shrink or adjust your state until the valid invariant is restored.

3. Time and Space Complexity Trade-Offs

In top-tier technical interviews at Google, Meta, and Amazon, arriving at a working solution is only half the battle. You must explicitly justify why your approach achieves optimal Big-O bounds. For Monotonic Stack, the target time complexity is typically O(n) — each element pushed/popped once while maintaining an auxiliary space complexity of O(n). Always discuss whether an in-place modification or two-pass traversal can save memory.

4. Common Interview Edge Cases to Test

Before informing your interviewer that you have completed coding, trace your logic against these standard high-failure test cases:

Empty inputs, single-element collections, or all-identical values.
Inputs with negative numbers, duplicates, or extreme values that could cause integer overflow.
Odd versus even length inputs when dealing with pointer convergence or tree midpoints.

Monotonic stacks solve next-greater-element and histogram problems in O(n). The pattern, both varian…