Monotonic stack

How does Monotonic stack work?

The stack holds indices, not values. Each index waits there for its answer.

Before pushing a new index, pop every index the new value beats. Each pop is an answer.

The comparison decides what you get. Pop while the top is smaller for next greater.

Flip the comparison to pop while the top is bigger. That gives next smaller.

Whatever survives on the stack never found an answer. Those slots keep the default.

The inner loop looks quadratic. Each index is pushed once and popped once, so the total is linear.

1. [0]Push index 0. Value 2 sits on the stack.
2. [0, 1]Value 1 loses to 2. Nothing pops, push index 1.
3. [2]Value 5 beats 1, then 2. Both pop, both answer 5.
4. [2, 3]Value 3 loses to 5. Push index 3.
5. [2, 3]Input ends. Indices 2 and 3 keep -1.

function nextGreater(nums) {
    const result = new Array(nums.length).fill(-1);
    const stack = [];
    for (let i = 0; i < nums.length; i++) {
        while (stack.length && nums[stack[stack.length - 1]] < nums[i]) {
            result[stack.pop()] = nums[i];
        }
        stack.push(i);
    }
    return result;
}

A worked example of Monotonic stack

Daily temperatures

You get a list of daily temperatures. For each day, count the days until a warmer one.

No warmer day means 0. Nested loops run in O(n squared) and time out at 100000 days.

This is next greater element, with a distance instead of a value.

Walk left to right. Pop every day on the stack that is colder than today.

Today is that day's first warmer one. The wait is the gap between the indices.

Days left on the stack never warmed up. They keep their 0.

function dailyTemperatures(temps) {
    const wait = new Array(temps.length).fill(0);
    const stack = []; // indices, coldest at the bottom

    for (let today = 0; today < temps.length; today++) {
        while (
            stack.length &&
            temps[stack[stack.length - 1]] < temps[today]
        ) {
            const colder = stack.pop();
            wait[colder] = today - colder;
        }
        stack.push(today);
    }

    return wait; // days still on the stack keep their 0
}

When should you use Monotonic stack?

These phrases in a problem statement point here:

• •next greater / next smaller element
• •daily temperatures until it gets warmer
• •largest rectangle in a histogram
• •trap rainwater between bars
• •span/streak that ends at the first bigger or smaller value

What is Monotonic stack confused with?

• Stack: A plain stack pops when you say so. A monotonic stack pops on a comparison.
• Monotonic deque: A deque also drops elements that fall out of a window. With no expiry by age, a stack is enough.
• Sliding window (variable): A window answers questions about a range. This stack answers about one boundary element per index.
• Binary heap: A heap gives the global maximum in O(log n). The stack gives the nearest bigger neighbour in O(1).
• Sorting with a comparator: Sorting throws away positions. Next greater questions are entirely about position.

Common mistakes with Monotonic stack

• Pushing values instead of indices

  You need the position to compute a distance. Push the index, read the value with temps[i].

• Getting the comparison backwards

  Smaller on top gives next greater. Bigger on top gives next smaller.

• Forgetting the leftovers

  Elements still on the stack found no answer. Decide their value up front: -1, 0, or the length.

• Mishandling equal values

  Strict < keeps duplicates on the stack, <= pops them. Test [2, 2, 2] before you trust it.

Which interview problems use Monotonic stack?

• Next greater element: The pattern with nothing hidden. Everything else is a rewording.
• Daily temperatures: Next greater, but it asks for the distance.
• Largest rectangle in a histogram: Each bar needs its first shorter neighbour on both sides.
• Trapping rain water: Water sits between a bar and the next taller one.
• Stock span: Next greater run backwards, counting days instead of values.
• Remove k digits: Pop bigger digits to leave the smallest number.
• Sum of subarray minimums: Each value owns a span bounded by smaller neighbours.

What is the time and space complexity of Monotonic stack?

O(n)

n up to 1e5 elements gives O(n). Each element is pushed once and popped at most once.