Lesson 2 · Advanced structures and algorithms

Monotonic Stacks

A monotonic stack is an ordinary stack that refuses to hold values out of order. Before every push it discards anything that would break the ordering, and each discarded value leaves with its answer already known. That single rule converts a family of O(N²) scanning problems into one linear pass.

A Stack That Refuses Disorder

A monotonic stack is an ordinary stack with one extra rule enforced on every push: before pushing, pop everything that would break the ordering. The stack's contents therefore stay sorted at all times, either increasing or decreasing from bottom to top.

The rule sounds like a constraint and is really a filter. Each pop discards an element that has just been proven useless — and the technique's power comes from the fact that the moment of discarding is exactly the moment its answer is known.

The problem it solves is the next greater element family: for each element in an array, find the nearest element to its right that is larger. The obvious solution scans forward from every position, giving O(n²). A monotonic stack does it in O(n).

The insight that makes this possible: when scanning left to right and encountering a value, any earlier element smaller than it can never be the answer for anything further right. If some later element is looking for a bigger neighbour, the current value blocks it — the current value is both larger and closer. So those smaller earlier elements can be discarded permanently, and their own answer is the value that just arrived.

Direction determines the ordering. To find the next greater element, maintain a decreasing stack — you pop smaller elements when a bigger one arrives, and that bigger one is their answer. To find the next smaller, maintain an increasing stack. The pairing is easy to get backwards; derive it from what you pop rather than memorising it.

Pop everything that breaks the ordering, then push
An element is popped exactly when its answer is found
Next greater needs a decreasing stack; next smaller an increasing one
Derive the direction from what gets popped, not from memory

The Pop Is the Answer

This is the sentence to carry away, and the reason the technique is not simply 'a stack that happens to be sorted'.

Work through next greater element concretely. Scan the array left to right, maintaining a stack of indices whose values decrease from bottom to top. At each index i, while the stack is non-empty and the value at the top is less than the value at i, pop that index and record that its next greater element is the value at i. Then push i.

Each popped element's answer is the current one, because the current element is the first value encountered that exceeds it — everything between them was smaller, or it would have been popped earlier. That 'first' is what makes it the next greater element rather than merely a greater element.

Store indices rather than values. The values are always retrievable as arr[stack.top()], but the indices are not recoverable from the values — and many problems need the distance rather than the value. The 'daily temperatures' problem asks how many days until a warmer day, which is i - poppedIndex; with values on the stack that answer is unavailable.

Whether to use < or <= in the pop condition is decided by duplicates. With strict <, equal elements do not pop each other, so an element's answer is the next strictly greater one. With <=, equal elements pop, and the answer becomes the next greater or equal. Neither is universally right — read the problem statement and choose deliberately, because this is the difference between a correct solution and one failing on repeated values.

The scanning direction can also be reversed. Scanning right to left with the same machinery finds the same answers, and some people find it more intuitive since the stack then holds candidate answers rather than pending questions. Both are O(n); pick one and be consistent.

Pop while the top is smaller, and record the current element as its answer
The current element is the first larger one, hence the next greater
Push indices so distances remain computable
< versus <= decides how duplicates are treated

Why It Is Linear

The code contains a while loop inside a for loop, which looks like it should be quadratic. It is not, and being able to explain why is what separates understanding the technique from having memorised it.

The argument is an amortised one. Each index is pushed onto the stack exactly once, at its own iteration. Each index is popped at most once, and once popped it is never reconsidered. So across the entire run, the total number of pops is bounded by n — not by n per iteration.

One iteration of the outer loop may pop many elements, but that only happens because earlier iterations pushed them, and each of those pushes has already been counted. The inner loop's total work over the whole algorithm is therefore O(n), not O(n) per step.

Total: O(n) time and O(n) space, the space being the stack, which in the worst case — a strictly decreasing input where nothing is ever popped early — holds all n elements.

This push-once-pop-once accounting is the same argument that makes the sliding window linear, and recognising it as a shared pattern is useful: whenever each element enters and leaves a structure at most once, nested loops do not imply quadratic behaviour.

The leftovers matter. When the scan finishes, whatever remains on the stack was never popped, which means no answer exists for those elements — nothing larger ever appeared to their right. They must be assigned an explicit sentinel, usually −1 or null, and forgetting this leaves those positions holding whatever the result array was initialised with. It is the single most common bug in monotonic stack code, and it only manifests on inputs whose maximum is not at the end.

For circular arrays, where the search wraps around, the standard technique is to iterate 2n times using i % n for indexing, pushing only during the first pass. That gives every element a full circuit's worth of candidates without duplicating the array.

Each index is pushed once and popped at most once — O(n) total
The inner loop's work is bounded across the run, not per iteration
Elements left on the stack have no answer — assign a sentinel
Circular variants iterate 2n times with modulo indexing

Key reference

Terms, operations, and practical uses

Invariants

Monotonic IncreasingA stack where every element from bottom to top is strictly smaller than the one above it.
Monotonic DecreasingA stack where every element from bottom to top is strictly larger than the one above it.
Conflict ResolutionPopping elements from the stack until the new element can be pushed without violating the monotonic invariant.

Mechanics

Index StorageStoring the array index rather than the value in the stack, allowing calculation of distances (widths) when an element is popped.
The PopperThe new element that forces existing elements off the stack. This element is by definition the 'next greater' or 'next smaller' element.
O(N) ComplexityDespite a while-loop inside a for-loop, the algorithm is O(N) because every element is pushed and popped exactly once.

Classic problems

Next Greater ElementFinding the first element to the right that is larger than the current element (e.g., Daily Temperatures).
Largest Rectangle in HistogramA famously difficult geometry problem reduced to O(N) time using a monotonic increasing stack.
Stock SpannerCalculating how many consecutive previous days had a stock price lower than or equal to today's price.

Implementation

Daily Temperatures (Next Greater Element)

def dailyTemperatures(temps):
    ans = [0] * len(temps)
    stack = [] # Stores indices, monotonically decreasing by temp

    for i, t in enumerate(temps):
        while stack and temps[stack[-1]] < t:
            prev_index = stack.pop()
            ans[prev_index] = i - prev_index
        stack.append(i)
    return ans
print('Wait days:', dailyTemperatures([73, 74, 75, 71, 69, 72]))

#include <iostream>
#include <vector>
#include <stack>
using namespace std;
vector<int> dailyTemperatures(vector<int>& temps) {
    vector<int> ans(temps.size(), 0);
    stack<int> st; // Stores indices
    for (int i = 0; i < temps.size(); i++) {
        while (!st.empty() && temps[st.top()] < temps[i]) {
            int prev_index = st.top();
            st.pop();
            ans[prev_index] = i - prev_index;
        }
        st.push(i);
    }
    return ans;
}
int main() {
    vector<int> temps = {73, 74, 75, 71, 69, 72};
    vector<int> ans = dailyTemperatures(temps);
    cout << "Wait days: [";
    for (size_t i = 0; i < ans.size(); i++) {
        if (i) cout << ", ";
        cout << ans[i];
    }
    cout << "]\n";
}

import java.util.*;
class Main {
    public int[] dailyTemperatures(int[] temps) {
        int[] ans = new int[temps.length];
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < temps.length; i++) {
            while (!stack.isEmpty() && temps[stack.peek()] < temps[i]) {
                int prevIndex = stack.pop();
                ans[prevIndex] = i - prevIndex;
            }
            stack.push(i);
        }
        return ans;
    }
    public static void main(String[] args) {
        int[] ans = new Main().dailyTemperatures(new int[]{73, 74, 75, 71, 69, 72});
        System.out.println("Wait days: " + Arrays.toString(ans));
    }
}

Watch it run

Step through it

Running on Temps: [73, 74, 75, 71, 69, 72]

Output

Read all 10 Steps

Day 0 — 73 The stack is empty, so nothing can be resolved yet. Push index 0 and move on. The stack holds days still waiting for a warmer one.
Day 1 — 74 breaks the invariant 74 is warmer than the 73 on top. A decreasing stack cannot hold 73 below 74, and that conflict is exactly the signal we want.
Pop 0 — answer found Popping resolves day 0: the value that forced the pop IS its next warmer day. ans[0] = 1 − 0 = 1. This is the whole trick.
Day 2 — 75 pops again 75 > 74, so day 1 resolves the same way: ans[1] = 2 − 1 = 1. Then push index 2. The stack never holds more than it needs.
Day 3 — 71 just stacks 71 < 75, so the invariant already holds and nothing pops. Day 3 joins the queue of unresolved days below the taller 75.
Day 4 — 69 stacks too 69 < 71, still decreasing. Three days are now unresolved, stored bottom-to-top in strictly decreasing temperature order.
Day 5 — 72 pops 69 72 > 69, so day 4 resolves: ans[4] = 5 − 4 = 1. One warm day can settle several older ones, so keep popping.
Day 5 — 72 pops 71 as well 72 is still greater than the new top, 71. ans[3] = 5 − 3 = 2. The stack being sorted is what lets one pass settle a whole run.
Day 5 — 72 stops at 75 72 < 75, so popping halts and index 5 is pushed. Day 2 keeps waiting because nothing warmer has arrived yet.
Input exhausted — leftovers are zero Days 2 and 5 are still on the stack, meaning no warmer day ever came: ans stays 0 for both. Every index was pushed once and popped at most once, so the scan is O(N), not O(N²).

Largest Rectangle in a Histogram

The hardest standard application, and the one that shows the technique doing something a simple scan cannot.

Given bar heights, find the largest rectangle fitting inside the histogram. A rectangle is determined by choosing a bar as its height and extending as far left and right as bars remain at least that tall. So for every bar, the question is: how far can it extend before hitting a shorter bar on each side?

Those are precisely the previous smaller and next smaller elements — both monotonic stack problems. With a increasing stack of indices, when a bar shorter than the top arrives, the popped bar's right boundary is the current index and its left boundary is whatever now sits below it on the stack. The width is the gap between those two boundaries, exclusive.

The width calculation is where implementations go wrong. After popping index top, the width is i - stack.top() - 1 using the new stack top after the pop, not the popped index itself. When the stack becomes empty after popping, the bar extends all the way to the left edge and the width is simply i.

That -1 and the empty-stack case are the two details worth writing out carefully rather than reconstructing under pressure.

A clean simplification: append a sentinel bar of height 0 to the end of the input. It is shorter than everything, so it forces every remaining bar to be popped and processed by the normal loop, eliminating the separate leftover-handling pass entirely. Some implementations prepend one too, removing the empty-stack special case.

The result is O(n) for a problem whose brute force is O(n²) — one pass, one stack.

The same shape solves maximal rectangle in a binary matrix: treat each row as the base of a histogram whose heights are the counts of consecutive 1s above, and run the histogram algorithm per row for O(rows × cols) overall. Trapping rain water is the other classic, computable with a monotonic stack though the two-pointer solution is simpler there.

Each bar's rectangle is bounded by the previous and next smaller bars
Width is i - stack.top() - 1 after the pop, using the new top
An empty stack after popping means the bar reaches the left edge
Append a zero-height sentinel to flush the stack in the main loop