Lesson 2 · Advanced structures and algorithms

Monotonic Stacks

A monotonic stack is a standard stack that enforces a strict rule (an invariant): its elements must always be sorted (monotonic) either in increasing or decreasing order. This constraint magically solves complex range-query problems in linear time.

Understanding 'Monotonic'

In mathematics, a monotonic function is one that never changes its trend. It either strictly goes up (increasing) or strictly goes down (decreasing).

A monotonic stack forces its contents to follow this trend. If it is a 'monotonically decreasing stack', the largest element is at the bottom, and every element above it is strictly smaller.

Monotonic increasing: [10, 20, 30, 40]
Monotonic decreasing: [40, 30, 20, 10]
Trend cannot reverse

Enforcing the Invariant

To maintain the monotonic property, you cannot simply push any new element. If you have a decreasing stack [40, 30, 20] and want to push 35, you must resolve the conflict.

You must pop elements from the stack until the new element can be pushed without breaking the rule. So you pop 20 and 30, then push 35, resulting in [40, 35].

Elements are popped to resolve conflicts
The invariant is never broken
Every element is pushed and popped at most once

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.

Code example

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 <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;
}

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;
    }
}

InputTemps: [73, 74, 75, 71, 69, 72]

OutputWait days: [1, 1, 0, 2, 1, 0]

Example

Run the example step by step

Output

The Next Greater Element

The magic of the monotonic stack is what happens during the 'pop' operation. When the new element 35 forced 20 and 30 to pop, 35 was exactly the Next Greater Element for both of them.

By tracking these pops, you can process an entire array and find the next greater element for every single item in just one O(N) pass, completely avoiding the naive O(N^2) nested loop.

The 'popper' is the Next Greater Element
Solves Daily Temperatures problems
Extremely fast O(N) time complexity

Largest Rectangle in Histogram

A monotonic increasing stack is the optimal solution for finding the largest rectangle in a histogram. The stack stores indices of bars.

When a shorter bar arrives, it forces taller bars to pop. The moment a tall bar is popped, we know its exact width (because it is bounded by the current short bar on the right, and the new top of the stack on the left).

Stores indices, not just values
Pops trigger area calculations
Reduces a complex geometry problem to O(N)