Monotonic Stack Explained | Backend Study Lab

Quick answer

A monotonic stack is a stack whose stored values stay in increasing or decreasing order. When a new value breaks that order, the algorithm pops elements until the invariant is restored. Those pops reveal relationships such as the next greater value, previous smaller value, span, or boundary of a histogram bar.

The pattern often replaces a nested scan with an O(n) pass. Although an element may appear inside a while loop, every index is pushed once and popped at most once. In Java, ArrayDeque<Integer> is usually the right stack implementation.

How to recognize the pattern

Look for a one-dimensional sequence and a question involving the nearest earlier or later element that is greater, smaller, warmer, taller, or otherwise crosses a threshold. Typical phrases include:

next greater or next smaller element;
previous greater or previous smaller element;
how many consecutive earlier values satisfy a condition;
how long until a higher value arrives;
the first boundary that makes a bar or range invalid;
maximum rectangle under a histogram;
remove dominated candidates while scanning.

The relationship must be local in order, even if the matching element is far away. If the problem asks for arbitrary range aggregates, a segment tree, sparse table, prefix structure, or sorting approach may fit better.

Another signal is repeated dominance: once a newer value proves an older candidate can never be the nearest valid answer for future positions, that older candidate can be removed permanently. Permanent elimination is what enables the amortized linear bound.

The invariant

Suppose the stack stores indices whose values are monotonically decreasing from bottom to top. When processing values[i], any smaller value at the top has found its next greater element: it is values[i].

For [2, 1, 2, 4, 3]:

i=0 value=2  stack values [2]
i=1 value=1  stack values [2,1]
i=2 value=2  pop 1 -> next greater is 2; stack [2,2]
i=3 value=4  pop 2 -> 4; pop 2 -> 4; stack [4]
i=4 value=3  stack values [4,3]
end           unresolved indices have no next greater value

The stack is not the answer itself. It is a compact set of unresolved candidates. A new value eliminates candidates it dominates and may become a candidate for later values.

Brute force first

A direct next-greater implementation scans to the right from every index:

static int[] nextGreaterBruteForce(int[] values) {
    int[] answer = new int[values.length];
    Arrays.fill(answer, -1);
    for (int i = 0; i < values.length; i++) {
        for (int j = i + 1; j < values.length; j++) {
            if (values[j] > values[i]) {
                answer[i] = values[j];
                break;
            }
        }
    }
    return answer;
}

This is easy to validate, but decreasing input such as [5,4,3,2,1] performs about n²/2 comparisons. The monotonic stack shares the unresolved work across all starting positions.

Java next greater implementation

Store indices because the output belongs to original positions:

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

static int[] nextGreater(int[] values) {
    if (values == null) {
        throw new IllegalArgumentException("values must not be null");
    }

    int[] answer = new int[values.length];
    Arrays.fill(answer, -1);
    Deque<Integer> indices = new ArrayDeque<>();

    for (int i = 0; i < values.length; i++) {
        while (!indices.isEmpty()
                && values[i] > values[indices.peekLast()]) {
            int resolvedIndex = indices.removeLast();
            answer[resolvedIndex] = values[i];
        }
        indices.addLast(i);
    }
    return answer;
}

peekLast, removeLast, and addLast make one end of the deque the stack top. Using a consistent end is more important than which end you choose. ArrayDeque rejects null elements and is not thread-safe, neither of which is a problem for local integer indices.

Strict versus non-strict comparisons

The comparison encodes the question. For next strictly greater, pop while the incoming value is >. Equal values remain unresolved because neither is greater.

For next greater-or-equal, pop with >=. For a monotonically increasing stack that finds next smaller, reverse the comparison.

Duplicates expose incorrect choices:

input: [2,2,3]
strict next greater: [3,3,-1]
greater-or-equal:    [2,3,-1]

Write the relationship in words before choosing <, <=, >, or >=. Then test equal values deliberately.

Store indices or values?

Store values only when the answer needs only a value and duplicates do not require identity. Store indices when you need:

the distance to the match;
an answer per input position;
left and right boundaries;
stable handling of equal values;
access to multiple arrays aligned by index.

Indices are the safer default. They preserve the value through values[index] and retain position without extra objects.

Daily temperatures pattern

For each day, return the number of days until a warmer temperature:

static int[] daysUntilWarmer(int[] temperatures) {
    if (temperatures == null) {
        throw new IllegalArgumentException("temperatures must not be null");
    }

    int[] waits = new int[temperatures.length];
    Deque<Integer> colderDays = new ArrayDeque<>();

    for (int day = 0; day < temperatures.length; day++) {
        while (!colderDays.isEmpty()
                && temperatures[day] > temperatures[colderDays.peekLast()]) {
            int colderDay = colderDays.removeLast();
            waits[colderDay] = day - colderDay;
        }
        colderDays.addLast(day);
    }
    return waits;
}

The stack remains decreasing by temperature. Unresolved days keep the default zero, matching “no warmer future day.”

Stock span pattern

Stock span asks how many consecutive days ending today have prices less than or equal to today’s price. Scan left to right with a decreasing stack. Pop prior prices <= current, then the remaining top is the nearest earlier strictly greater price:

static int[] stockSpan(int[] prices) {
    int[] spans = new int[prices.length];
    Deque<Integer> greaterDays = new ArrayDeque<>();

    for (int day = 0; day < prices.length; day++) {
        while (!greaterDays.isEmpty()
                && prices[greaterDays.peekLast()] <= prices[day]) {
            greaterDays.removeLast();
        }
        spans[day] = greaterDays.isEmpty()
                ? day + 1
                : day - greaterDays.peekLast();
        greaterDays.addLast(day);
    }
    return spans;
}

Here equal prices are included in the span, so the condition deliberately uses <=.

Largest rectangle connection

In the largest-rectangle-in-histogram problem, every bar needs the first shorter boundary on both sides. An increasing stack tracks bars whose right boundary is unknown. When a shorter bar arrives, popped bars use the new index as their exclusive right boundary and the new stack top as their previous-shorter boundary.

A sentinel height of zero at the end flushes unresolved bars:

static long largestRectangle(int[] heights) {
    Deque<Integer> stack = new ArrayDeque<>();
    long best = 0;

    for (int i = 0; i <= heights.length; i++) {
        int current = i == heights.length ? 0 : heights[i];
        while (!stack.isEmpty()
                && current < heights[stack.peekLast()]) {
            int height = heights[stack.removeLast()];
            int leftExclusive = stack.isEmpty() ? -1 : stack.peekLast();
            long width = i - leftExclusive - 1L;
            best = Math.max(best, width * height);
        }
        if (i < heights.length) {
            stack.addLast(i);
        }
    }
    return best;
}

Use long for area because int * int can overflow before assignment. Validate whether negative heights are allowed; ordinary histogram formulations require nonnegative input.

Why the algorithm is O(n)

The inner loop does not make the algorithm quadratic. Charge work to elements:

each index is pushed exactly once;
each index is popped at most once;
other work per iteration is constant.

Across the whole scan there are at most n pushes and n pops, so time is O(n). The stack may contain all indices for a monotonic input, so auxiliary space is O(n).

This amortized argument matters whenever a loop removes candidates permanently. If candidates can be reinserted or rescanned, the same proof may not apply.

Direction matters

Scanning left to right naturally resolves “next” relationships when the future value arrives, and “previous” relationships by inspecting the top before pushing.

Scanning right to left can produce next relationships directly for each current item. Both styles are valid. Choose the direction that makes the invariant and output simplest, then state it:

scan left to right + pop unresolved indices
scan right to left + top is already the nearest valid future candidate

Avoid switching styles midway through a proof.

Testing the Java code

Example JUnit 5 cases:

@Test
void findsNextStrictlyGreaterValues() {
    assertArrayEquals(
        new int[] {4, 2, 4, -1, -1},
        nextGreater(new int[] {2, 1, 2, 4, 3})
    );
}

@Test
void equalValuesAreNotStrictlyGreater() {
    assertArrayEquals(
        new int[] {3, 3, -1},
        nextGreater(new int[] {2, 2, 3})
    );
}

@Test
void handlesEmptyInput() {
    assertArrayEquals(new int[0], nextGreater(new int[0]));
}

@Test
void rejectsNullInput() {
    assertThrows(IllegalArgumentException.class, () -> nextGreater(null));
}

Also compare randomized small arrays against the brute-force implementation. Differential tests are excellent for catching a reversed comparison or incorrect duplicate policy.

Common mistakes

The first mistake is memorizing code without writing the invariant. A decreasing stack for next greater and an increasing stack for next smaller look similar but answer different questions.

The second is storing values when the result needs indices or distances.

The third is choosing strictness accidentally. Duplicates must appear in tests.

The fourth is claiming the while loop makes the algorithm O(n²) or claiming linear time without the push/pop proof.

The fifth is using Java’s legacy Stack class by habit. ArrayDeque provides the intended deque operations for local stack usage.

The sixth is forgetting unresolved elements. Decide whether they remain -1, zero, array length, or a caller-defined sentinel.

The seventh is overflowing width-times-height calculations in histogram variants.

Practical checklist

Identify a nearest greater/smaller or boundary relationship.
State whether the stack is increasing or decreasing.
State whether equality should pop.
Decide whether the stack stores indices, values, or records.
Choose scan direction and explain it.
Initialize the unresolved-result sentinel.
Prove every item is pushed once and popped at most once.
Use ArrayDeque, consistently operating on one end.
Test empty, single, monotonic, duplicate, and all-equal input.
Compare randomized small inputs with a brute-force oracle.
Use long when derived products can overflow.
Link the pattern back to the broader Algorithms learning path and topic clusters.

Frequently asked questions

Is a monotonic stack a special Java collection?

No. It is an invariant maintained by the algorithm. A normal ArrayDeque becomes monotonic because your push/pop logic preserves an order.

Why not sort the input?

Sorting destroys the original nearest-position relationship. The stack processes values in sequence order and retains unresolved indices.

Can the stack contain equal values?

Yes, if the target relationship is strict. If equality should resolve or merge candidates, use a non-strict pop or store counts/boundaries explicitly.

Is every next-greater problem linear?

The standard array version is. Variants with dynamic updates, arbitrary range queries, or additional constraints may require other structures.

When should I use a deque instead?

A sliding-window maximum normally needs candidates removed from both ends, so it uses a monotonic deque rather than a one-ended stack.

Sources and further reading

Oracle, ArrayDeque in Java SE 25.
Oracle, Deque in Java SE 25.
Princeton Algorithms, Stacks and Queues.

Continue with Queue vs Deque in Java for Java container choices, Big-O Notation Explained for amortized analysis, and Sliding Window Algorithm Explained for monotonic deque variants. Browse the Algorithms learning path and topic clusters for the full sequence.