Stacks and Monotonic Stacks | Developer Knowledge Base

Stacks turn control flow into data: they model LIFO behavior, expose hidden nesting, and become especially powerful when a monotonic invariant lets one pass answer “next greater”, “next smaller”, and similar boundary questions.

1. Definition

What is a stack?

A stack is a Last-In, First-Out data structure. The last element pushed in is the first element popped out. The core operations are push, pop, peek, and often isEmpty.

Why does it exist?

A stack exists because many problems naturally care about the most recent unresolved item.

That happens in:

nested structures,
undo-like flows,
recursion,
expression parsing,
and “wait until something stronger appears” patterns.

What is a monotonic stack?

A monotonic stack is a stack that maintains an order invariant.

Typical forms:

increasing stack,
decreasing stack.

The stack is not just storing values.

It stores candidates that remain useful under a specific ordering rule.

Where does it fit?

This topic matters when the problem mentions:

balanced parentheses,
nearest greater element,
nearest smaller element,
daily temperatures,
stock span,
histogram boundary reasoning,
or anything that sounds like “for each item, find the next/previous item that breaks a condition”.

Intuition

A normal stack is like a pile of plates.

You take from the top.

A monotonic stack is like a pile where you keep removing weaker plates until the top is meaningful again.

It is a filtering mechanism, not just a container.

Java context

In Java interview code, prefer Deque for stack behavior.

ArrayDeque is the standard practical choice.

Example:

Deque<Integer> stack = new ArrayDeque<>();
stack.push(10);
stack.push(20);
int top = stack.peek();
int removed = stack.pop();

The old Stack class exists, but it is usually not the recommended modern API.

2. Core Concepts

2.1 LIFO behavior

The defining rule is LIFO.

That means the structure is ideal when the most recent unresolved item should be processed first.

Examples:

nested parentheses,
recursive calls,
path backtracking,
undo history.

2.2 Core operations and complexity

Operation	Complexity	Meaning
`push`	`O(1)` amortized	Put a new element on top
`pop`	`O(1)`	Remove the top element
`peek`	`O(1)`	Inspect the top without removing it
`isEmpty`	`O(1)`	Check whether unresolved items remain

2.3 Why stacks solve nesting problems

When something opens and later closes, the most recent opener is the one that must be resolved first.

That is exactly LIFO.

Balanced parentheses are the cleanest example.

When you see a closing bracket, you compare it with the most recent unmatched opening bracket.

2.4 Stack vs recursion

The call stack used by recursion is also a stack.

That is why recursive DFS and explicit stack-based DFS are closely related.

Interviewers often want you to notice that connection.

2.5 Monotonic invariant

A monotonic stack adds an ordering rule.

For a decreasing stack:

the values from bottom to top stay decreasing,
smaller values get popped when a bigger value arrives.

For an increasing stack:

values from bottom to top stay increasing,
larger values get popped when a smaller value arrives.

The exact direction depends on the question.

2.6 Why monotonic stacks are powerful

They let one pass solve problems that look quadratic at first.

Naive version:

for every index, scan to the right until a qualifying element is found.

That is often O(n^2).

Monotonic stack version:

keep only unresolved candidates,
resolve them when a stronger element appears,
each element is pushed once and popped once.

That gives O(n).

2.7 Values vs indices

A very important detail:

many monotonic stack problems should store indices, not values.

Why indices are often better:

they let you compute distances,
they let you read original values from the array,
and they handle duplicates more reliably.

For example, in Daily Temperatures, the answer is a distance, so index storage is natural.

2.8 Previous vs next element variants

There are four common versions:

next greater,
next smaller,
previous greater,
previous smaller.

The loop direction and pop condition change, but the core pattern is the same.

2.9 Equality handling matters

One subtle bug source is whether the pop condition should use:

<,
<=,
>,
or >=.

That depends on whether equal values should stay or be removed.

This is not a cosmetic detail.

It changes correctness for duplicates.

2.10 Recognition signals

A monotonic stack should come to mind when:

the problem asks for the next or previous stronger/weaker item,
brute force scans left/right from every element,
the answer depends on nearest boundaries,
or each element seems to “wait” for a better future match.

2.11 Amortized reasoning

Monotonic stack solutions are often explained with amortized complexity.

Although one loop iteration may pop multiple items, each item can only be pushed once and popped once.

So total stack work over the whole input remains linear.

3. Practical Usage

When to use a normal stack

A plain stack is the right fit when the task is about:

matching nested symbols,
undo-like workflows,
backtracking support,
iterative DFS,
or evaluating expressions in reverse dependency order.

Classic examples:

valid parentheses,
simplify path,
browser history model,
DFS without recursion.

When to use a monotonic stack

Use a monotonic stack when the task is about nearest boundaries under an order rule.

Typical examples:

next greater element,
daily temperatures,
stock span,
largest rectangle in histogram,
trapping/range boundary preparation,
or removing dominated candidates online.

When NOT to use a stack

Do not force stack thinking if:

the problem is mainly FIFO,
global sorting solves it more simply,
prefix sums or two pointers are more natural,
or you do not need “most recent unresolved item” behavior.

Java-specific guidance

Prefer:

Deque<Integer> stack = new ArrayDeque<>();

Avoid using the old Stack class in most modern Java code unless you have a very specific reason.

For monotonic stacks, ArrayDeque<Integer> is also the usual best choice.

Pair-programming angle

A strong explanation sounds like this:

“I’ll use a decreasing stack of indices.”
“While the current value is greater than the value at the stack top, I can resolve those waiting indices.”
“Each index enters once and leaves once, so total work is linear.”

That explanation is far stronger than simply saying "this is a monotonic stack problem."

LeetCode #20 — Valid Parentheses — classic stack matching exercise.
LeetCode #739 — Daily Temperatures — monotonic decreasing stack with index tracking.
LeetCode #496 — Next Greater Element I — monotonic stack + HashMap for lookup.
LeetCode #84 — Largest Rectangle in Histogram — monotonic stack for span calculation.
LeetCode #155 — Min Stack — auxiliary stack to maintain running minimum.

4. Code Examples

Basic Example

This validates parentheses using a stack.

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.Map;

public class ValidParenthesesExample {
    public static boolean isValid(String text) {
        Deque<Character> stack = new ArrayDeque<>();
        Map<Character, Character> closingToOpening = Map.of(
                ')', '(',
                ']', '[',
                '}', '{'
        );

        for (char current : text.toCharArray()) {
            if (current == '(' || current == '[' || current == '{') {
                stack.push(current);
            } else {
                if (stack.isEmpty() || stack.pop() != closingToOpening.get(current)) {
                    return false;
                }
            }
        }

        return stack.isEmpty();
    }
}

Why it works:

openers are unresolved work,
closers must match the most recent unresolved opener,
and leftover openers mean the nesting is incomplete.

Advanced Example

This solves Next Greater Element to the right with a monotonic stack of indices.

import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;

public class NextGreaterElementExample {
    public static int[] nextGreater(int[] nums) {
        int[] answer = new int[nums.length];
        Arrays.fill(answer, -1);

        Deque<Integer> stack = new ArrayDeque<>();

        for (int index = 0; index < nums.length; index++) {
            while (!stack.isEmpty() && nums[index] > nums[stack.peek()]) {
                int resolvedIndex = stack.pop();
                answer[resolvedIndex] = nums[index];
            }
            stack.push(index);
        }

        return answer;
    }
}

Key invariant:

the stack holds indices whose next greater element has not yet been found,
values at those indices are monotonic with the chosen rule,
and the current number resolves weaker candidates.

Common Pitfall

This version stores values instead of indices for a distance-based problem.

import java.util.ArrayDeque;
import java.util.Deque;

public class BrokenDailyTemperaturesIdea {
    public static void broken(int[] temperatures) {
        Deque<Integer> stack = new ArrayDeque<>();

        for (int temperature : temperatures) {
            while (!stack.isEmpty() && temperature > stack.peek()) {
                stack.pop();
            }
            stack.push(temperature);
        }
    }
}

Why it is wrong:

values alone do not tell you where the unresolved day is,
so you cannot compute distances,
and duplicates become ambiguous.

For distance or boundary output, indices are usually the right state.

Another useful pattern: Daily Temperatures

import java.util.ArrayDeque;
import java.util.Deque;

public class DailyTemperaturesExample {
    public static int[] solve(int[] temperatures) {
        int[] answer = new int[temperatures.length];
        Deque<Integer> stack = new ArrayDeque<>();

        for (int index = 0; index < temperatures.length; index++) {
            while (!stack.isEmpty() && temperatures[index] > temperatures[stack.peek()]) {
                int previousIndex = stack.pop();
                answer[previousIndex] = index - previousIndex;
            }
            stack.push(index);
        }

        return answer;
    }
}

This is one of the cleanest interview demonstrations of monotonic-stack value.

5. Trade-offs

Aspect	Details
⚡ Performance	Stack operations are constant time; monotonic stacks often reduce `O(n^2)` scans to `O(n)` via amortized push/pop behavior
💾 Memory	Requires extra stack storage, often `O(n)` in the worst case
🔧 Maintainability	Simple when the invariant is stated clearly; confusing when the pop condition is unexplained
🔄 Flexibility	Excellent for nesting, nearest-boundary, and deferred-resolution problems

Performance nuance

Monotonic stacks are not magic.

They work because each element participates a limited number of times.

If you cannot explain that “push once, pop once” story, you do not yet own the pattern.

Memory nuance

The extra stack is usually the trade-off you accept to avoid repeated scanning.

That is often a strong exchange.

Readability nuance

The hardest part for readers is usually the while-loop condition.

Name the invariant explicitly.

For example:

“decreasing stack of indices waiting for a greater value”,
“increasing stack of candidate minima”,
“open brackets waiting to be closed”.

6. Common Mistakes

Using the wrong API type — In Java, many candidates still use Stack instead of Deque. The modern default is usually ArrayDeque.
Storing values when indices are needed — If the answer depends on distance or original position, value-only storage breaks the solution.
Choosing the wrong pop condition — > versus >= or < versus <= changes duplicate handling and can silently break correctness.
Forgetting to process leftovers conceptually — In next-greater style problems, unresolved items often keep default answers such as -1 or 0.
Not stating the invariant — Without a clear monotonic rule, the code becomes memorized ceremony instead of understandable logic.
Mixing FIFO and LIFO thinking — Some problems need queues, not stacks. If the oldest item should be processed first, a stack is the wrong model.
Pushing too early or too late — In monotonic logic, the order “resolve while needed, then push current” is often essential.

Debugging tip

Print or sketch the stack after each step for a tiny input.

If you cannot explain why each element remains there, the invariant is probably wrong.

7. Deep Dive

Why balanced parentheses is such a foundational problem

Because it shows the pure LIFO story with almost no noise.

You learn that:

unresolved openers are state,
the newest unresolved opener matters most,
and the structure is correct only if nothing unresolved remains at the end.

That same logic appears in more advanced parser and traversal problems.

Why monotonic stacks feel unintuitive at first

Because the stack is not modeling time alone.

It is modeling unresolved candidates under an order rule.

You are not keeping everything.

You are keeping only the elements still capable of influencing a future answer.

Monotonic stacks are online filters

That is a powerful mental model.

As each new element arrives:

weaker candidates are discarded,
unresolved stronger candidates remain,
and the current element joins only if it still matters.

This is why many solutions feel both greedy and structured at the same time.

Equality is often the real interview trap

Consider duplicates.

Should equal values resolve each other?

Sometimes yes.

Sometimes no.

This is exactly why “I know the monotonic stack template” is not enough.

You must reason about the comparison operator from the problem semantics.

Largest Rectangle in Histogram connection

Histogram and boundary-area problems are where monotonic stacks become more advanced.

There the stack is not just returning next greater/smaller values.

It is identifying maximal spans where a bar can remain the limiting height.

That is a deep extension of the same core invariant.

Pair-programming scenario

Imagine you are explaining Daily Temperatures.

A strong narrative is:

each day waits for a warmer future day,
the stack stores indices of waiting days,
temperatures at those indices stay monotonic,
a warmer day resolves all weaker waiting days on top,
each index enters once and exits once,
so the solution is linear.

That style of explanation shows ownership, not memorization.

8. Interview Questions

Q: Why is a stack the right structure for balanced parentheses? — A: Because closing brackets must match the most recent unmatched opening bracket. That is exactly LIFO behavior.

Q: Why do many monotonic-stack problems store indices instead of values? — A: Because indices let you compute distances, access original values, and handle duplicates more safely.

Q: Why is a monotonic-stack solution often O(n) instead of O(n^2)? — A: Because each element is pushed at most once and popped at most once, so total stack work across the input is linear.

Q: What is the hardest part of monotonic-stack correctness? — A: Choosing the right invariant and comparison condition, especially when equal values exist.

Q: Why should Java interview code usually use Deque instead of Stack? — A: Deque with ArrayDeque is the more modern and typically preferred API for stack semantics in Java.

9. Glossary

Term	Definition
LIFO	Last-In, First-Out behavior where the newest element is removed first
monotonic stack	A stack that preserves an increasing or decreasing ordering invariant
unresolved candidate	An item still waiting for a future element to determine its answer
next greater element	The first later element that is strictly greater than the current one
deferred resolution	A strategy where items stay stored until a later event resolves them
amortized analysis	Reasoning about total cost across all operations rather than one expensive step in isolation

10. Cheatsheet

Use a stack when the newest unresolved item matters most.
Use Deque / ArrayDeque for stack behavior in Java.
Balanced parentheses is the cleanest LIFO example.
Monotonic stacks solve nearest-boundary problems efficiently.
Many monotonic problems should store indices, not values.
State the invariant: increasing or decreasing, values or indices, waiting for what?
Watch duplicate handling carefully in the pop condition.
“Push once, pop once” is the key amortized-complexity story.
If the oldest item matters first, you probably need a queue, not a stack.
If you cannot explain why the top stays on the stack, you do not yet trust the invariant.