Monotonic Stack: Complete Guide with Examples

The monotonic stack answers one specific question and answers it fast: for each element in an array, what is the nearest element to the left or right that is greater or smaller than it? A brute-force loop checks every pair of elements, which costs

Definition: a monotonic stack is a stack that stays sorted at all times. Every push first removes the elements from the top that break the sorted order, then adds the new element. Whether it stays increasing or decreasing depends on the question you are answering, but the shape of the code barely changes.

Real-World Analogy

Picture a single line waiting at a ticket booth. Everyone in the line wants to know one thing: who is the closest person ahead of them who is taller than they are.

A short person standing in front of a taller one can never be the answer for anyone behind them, because the taller person hides them. So as the line forms, you never bother remembering a short person once a taller latecomer slots in front of them. You keep only the decreasing run of heights: the smallest, then the next taller one behind it, and so on. When a new tall person steps into the line, they immediately become the answer for everyone who has been waiting for a taller person, which is everyone in the run shorter than them. Those people stop waiting and leave the list. The list you keep is the monotonic stack.

Visual Explanation

The classic demo is Next Greater Element on the array [2, 1, 5, 6, 2, 3]. We walk left to right, and the stack holds the indices of elements that have not found their next greater value yet. Each pop resolves one answer.

    graph TD
    A["Array: 2, 1, 5, 6, 2, 3"] --> B["i=0: 2 goes on the stack"]
    B --> C["i=1: 1 fits below 2, stack is [2, 1]"]
    C --> D["i=2: 5 > 1, pop 1. answer[1] = 5"]
    D --> E["i=2: 5 > 2, pop 0. answer[0] = 5"]
    E --> F["i=2: stack empty, push 5"]
    F --> G["i=3: 6 > 5, pop 2. answer[2] = 6. push 6"]
    G --> H["i=4: 2 is not greater than 6. push 2"]
    H --> I["i=5: 3 > 2, pop 4. answer[4] = 3. push 3"]
    I --> J["Done. answers: 5, 5, 6, -1, 3, -1"]
  

The stack stays decreasing in value from bottom to top: [2, 1], then [5], then [6], then [6, 2], then [6, 3]. The rule is simple. When a new value arrives, every stack element smaller than it has waited long enough. Their next greater element is this new value, so we pop them, write the answer, and keep going until the stack top is no longer smaller.

When to Use This Pattern

Use a monotonic stack when the problem has these characteristics:

• The answer for each position depends on the nearest element to its left or right that beats a comparison, like “next greater” or “previous smaller.”
• The distances between positions matter, not just values. The Daily Temperatures family asks how many positions away the next greater value sits, and storing indices makes that subtraction trivial.
• Boundaries are defined by the nearest smaller elements. Largest Rectangle in Histogram needs, for each bar, the closest smaller height on each side to know how far the rectangle can stretch.
• The brute-force solution scans the array once per element, and you can see that each element only needs one comparison against its neighbors.
• You are building the lexicographically smallest sequence under a removal budget, like Remove K Digits, where a greedy pop of larger digits is exactly a monotonic stack operation.

Complexity Analysis

Each element enters the stack once and leaves once. There is no nested scanning, so the total work is one pass with stack maintenance.

The time bound is the reason this pattern exists. A naive double loop is

The space bound is the size of the stack in the worst case. A strictly increasing array never pops anything while computing next greater elements, so the stack grows to N.

Common Mistakes

Using the wrong traversal direction. To find the next greater element (to the right), scan left to right and pop when the current value beats the stack top. To find the previous one, you still scan left to right, but instead of popping into the result you pop until the top is greater than the current value, and that top is the answer. The two variants look similar and produce different results. A useful habit during practice: state out loud whether the answer walks left or right before you decide what to do with the stack top.

Storing values instead of indices. If you push values, you cannot update the result at the correct position, and you cannot compute distances. Push indices, then read nums[stack_top] when you need the value. Almost every monotonic problem on LeetCode stores indices for this reason.

Forgetting the knock-on effect of > vs >=. Next greater means strictly greater. When a tied value arrives, you must not pop the matching stack top, otherwise the equal element gets answered by itself and the answer is wrong. Duplicate-heavy test cases like [2, 2, 2, 3] instantly expose this.

Enforcing the sorted order only sometimes. The monotonic property holds only while every push keeps the order, which means every offending element above gets popped. A stack that occasionally skips the popping is just an O(N) storage layered on O(N^2) work. Test the ordering with a small descending input to see both the order maintenance and the space worst case, and confirm every push logically maintains the order.

Related Patterns

• Stack . The monotonic stack is a specialty of the basic stack. The stack page covers LIFO mechanics, expression evaluation, and when a plain stack suffices.
• Queue . The monotonic deque is the same idea shaped for sliding windows, where the oldest candidate also needs to expire. Sliding Window Maximum lives there.
• Sliding Window . If the problem involves a window that grows and shrinks while you track an extreme value inside, search for a deque-based maintenance (the queue page) rather than a stack.

Next Steps

Once the concept is clear, the next step is making the code automatic. Check out the code templates for memorizable implementations in six languages, then work through the practice problems to apply the pattern to real interview questions.