Monotonic stack: next greater element in a single pass

← Back to the section

We already know the stack as a "last in, first out" structure. It turns out that if the stack is kept ordered, it solves a whole class of problems that otherwise need nested loops.

The questions look like this: "for each day, how many days until revenue first goes higher?", "which is the nearest column to the left that is taller than this one?".

The problem

Take revenue by day and, for each day, find how many days pass before it first grows. The naive solution runs forward from every day until it meets a greater value:

for (int i = 0; i < revenue.length; i++) {
    for (int j = i + 1; j < revenue.length; j++) {
        if (revenue[j] > revenue[i]) { answer[i] = j - i; break; }
    }
}

That is O(N²). And the work is repeated: if revenue falls for a long time, every day scans the same tail again.

The idea: a queue of the waiting

Notice this: while revenue is falling, each new day is of no help to the previous ones — it is smaller, after all. All of them are "waiting" for a day that turns out to be higher. And when such a day finally arrives, it closes all of them at once.

So we need to keep the days that are still waiting for their growth. A stack is the convenient place: the last one to arrive is the freshest and the lowest, and it will be closed first.

The stack holds indices, not values: an index gives both the revenue and the distance in days. The days left in the stack at the end never saw growth — their answer is zero, and it is already there, because a Java array comes filled with zeros.

live example

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

public class DaysToGrow {
    public static void main(String[] args) {
        int[] revenue = {70, 60, 50, 90, 80, 120};
        int[] answer = new int[revenue.length];
        Deque<Integer> waiting = new ArrayDeque<>();
        int pops = 0;
        for (int i = 0; i < revenue.length; i++) {
            while (!waiting.isEmpty() && revenue[i] > revenue[waiting.peek()]) {
                int day = waiting.pop();
                answer[day] = i - day;
                pops++;
            }
            waiting.push(i);
        }
        System.out.println("revenue: " + Arrays.toString(revenue));
        System.out.println("wait:    " + Arrays.toString(answer));
        System.out.println("pops: " + pops + " for " + revenue.length + " days");
    }
}

The stack here is monotonic: from top to bottom the revenue in it grows. Every new day "cuts away" everything below it before being pushed.

Why this is linear despite the inner loop

A while inside a for is unsettling — it looks like O(N²). But count stack operations instead of iterations: every day is pushed exactly once and popped at most once. That is what the pops counter prints: five pops for six days, and there will never be more than six.

This way of counting is called an amortized estimate: a single step can be expensive, but the total work is bounded. The result is O(N) in time and O(N) in memory in the worst case, when the data falls monotonically and nobody is closed until the very end.

Strict or non-strict comparison

The code says revenue[i] > revenue[waiting.peek()] — strictly greater. That is not a detail: on data with repeats the two variants diverge immediately.

live example

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

public class StrictOrNot {
    public static void main(String[] args) {
        System.out.println("strict      > : " + days(true));
        System.out.println("non-strict >= : " + days(false));
    }

    static String days(boolean strict) {
        int[] revenue = {5, 5, 5};
        int[] answer = new int[revenue.length];
        Deque<Integer> waiting = new ArrayDeque<>();
        for (int i = 0; i < revenue.length; i++) {
            while (!waiting.isEmpty() && (strict
                    ? revenue[i] > revenue[waiting.peek()]
                    : revenue[i] >= revenue[waiting.peek()])) {
                int day = waiting.pop();
                answer[day] = i - day;
            }
            waiting.push(i);
        }
        return Arrays.toString(answer);
    }
}

With >= equal values start closing each other: on {5, 5, 5} the first day gets the answer "one day later", although there was no growth — the revenue stayed the same. The choice follows the wording: "strictly greater" or "not smaller". This is the most common mistake in the technique.

The direction is adjustable too: to look for the nearest greater element on the left, walk the array from right to left; to look for a smaller one, flip the comparison sign.

Monotonic deque

A related technique is needed when the maximum in a sliding window is wanted. A stack is no longer enough: elements leave not only from the top (a greater one pushed them out) but also from the bottom (they fell out of the window). The answer is a queue with access at both ends — the same ArrayDeque:

• from the tail, remove everyone smaller than the new element (they will never be the maximum again);
• from the head, remove those that went past the left edge of the window;
• the maximum of the window always sits at the head.

The time is O(N) too, and for the same reason: every element enters and leaves once.

How to recognise the technique

• The wording contains "nearest greater", "next smaller", "after how many steps does it first".
• The naive solution is a nested loop that runs forward or backward to the first matching element.
• A maximum or a minimum in a sliding window is needed — that is a monotonic deque.
• The largest rectangle in a histogram or the water trapped between columns — the same technique in different clothes.

How this is done in Java

There is no need to write your own stack: the standard library has one, and it is already used in the examples above. What is worth understanding is something else — what stands behind it.

ArrayDeque is a plain array plus two indices, head and tail, wrapping around the edge back to the start of the array; when there is no more room, the contents move into a bigger array. Everything the technique needs costs O(1) amortized: push puts an element at the head, pop takes it from there, peek looks at the top without removing it.

The same class covers the monotonic deque: a stack needs three methods at one end, a deque needs both — peekLast and pollLast at the tail, pollFirst at the head. Moving from a stack to a deque, you do not change the structure, only the calls.

The Stack class from the first versions of Java is not used for this: inside it is a Vector, every method is synchronized — you pay for locks even in a single thread that does not need them — and it iterates bottom-up, the reverse of the order in which it hands elements back. The details are in the article on stacks and queues.

The trap shows up exactly in the monotonic technique. The stack holds indices, so the type is Deque<Integer> — objects, and the line revenue[waiting.peek()] unboxes back into a number every time. On an empty stack peek() returns null, and unboxing null gives a NullPointerException — on a line where no explicit null is written. That is why the !waiting.isEmpty() check stands first in the while condition: short-circuit && is the only thing that keeps the second half from running. Swap them and the code falls on the very first element.

In short

• A monotonic stack keeps the elements that still await an answer in order; a new element closes everyone it beats at once.
• It holds indices, not values: an index gives both the value and the distance.
• The time is O(N) despite the nested loop: every element is pushed and popped at most once.
• Strict > or non-strict >= follows the wording; on data with repeats the mistake shows up immediately.
• The related technique is a monotonic deque for the sliding-window maximum: it drops smaller elements at the tail and out-of-window ones at the head.
• Take ArrayDeque, not Stack; the emptiness check goes before peek(), or unboxing null brings the code down.

What to read next

• Stacks and queues — the structure the whole technique rests on.
• Two pointers and the sliding window — the window that needs a monotonic deque.
• The maths behind big O — why a sum of bounded steps gives O(N).
• Choosing a data structure — when a stack wins over a tree or a hash table.