Monotonic Stack

Abstract

A monotonic stack is a stack maintained in strictly increasing or decreasing order (bottom to top) as you traverse the array. Pop elements until the new element respects the order, then push—this yields mappings for next/previous greater or smaller element.

A monotonic stack is a stack that stays in strictly increasing or strictly decreasing order from bottom to top while you process the array. When you push a new element, you pop from the top until the stack again satisfies that order. That process gives you, for each index, the next or previous element that is greater or smaller—the core idea behind many range and span problems.

The key idea

While traversing the array, before pushing an element, pop from the stack until the monotonic condition holds again (either increasing or decreasing). Each pop gives you a mapping: the element you pop has found its “next greater” or “next smaller” (depending on whether the stack is decreasing or increasing). So in one pass you can compute next/previous greater or next/previous smaller for every index.

Common patterns

Monotonic decreasing stack

Values in the stack decrease from bottom to top. You push only when the new value is ≤ the current top (after popping larger tops). When you pop, the current element is the next greater for the popped index.

Bottom → Top:  [75,  71,  69]   (rightmost is top)
                ↑         ↑
              bottom    top

Use when: Next Greater Element, Previous Greater Element, Daily Temperatures, Stock Span, “first greater on the right”

Monotonic increasing stack

Values in the stack increase from bottom to top. You push only when the new value is ≥ the current top (after popping smaller tops). When you pop, the current element is the next smaller for the popped index.

Bottom → Top:  [69,  71,  75]   (rightmost is top)
                ↑         ↑
              bottom    top

Use when: Next Smaller Element, Previous Smaller Element, Largest Rectangle in Histogram, Sum of Subarray Minimums, “first smaller on the right”

Example: Monotonic decreasing — Daily Temperatures (Next Greater)

For each day, find how many days you must wait until a warmer day. Store indices in a decreasing stack (by temperature). When the current temperature is greater than the temperature at the index on top, pop that index and set res[popped] = i - popped; then push the current index. Returns 0-indexed distances (or 0 if no warmer day).

T: [73, 74, 75, 71, 69, 72, 76, 73]
i=0: stack=[0]           (73)
i=1: 74>73 → pop 0, res[0]=1; stack=[1]
i=2: 75>74 → pop 1, res[1]=1; stack=[2]
i=3: 71≤75 → stack=[2,3]
i=4: 69≤71 → stack=[2,3,4]
i=5: 72>69 → pop 4, res[4]=1; 72>71 → pop 3, res[3]=2; 72≤75 → stack=[2,5]
i=6: 76>72 → pop 5, res[5]=1; 76>75 → pop 2, res[2]=4; stack=[6]
i=7: 73≤76 → stack=[6,7]
res = [1, 1, 4, 2, 1, 1, 0, 0]

Python

def dailyTemperatures(temperatures: list[int]) -> list[int]:
    stack: list[int] = []  # indices; decreasing stack (bottom to top) by value
    res = [0] * len(temperatures)
    for i, t in enumerate(temperatures):
        while stack and t > temperatures[stack[-1]]:
            j = stack.pop()
            res[j] = i - j
        stack.append(i)
    return res

C++

vector<int> dailyTemperatures(vector<int>& temperatures) {
    vector<int> stack;  // indices; decreasing stack (bottom to top) by value
    vector<int> res(temperatures.size(), 0);
    for (int i = 0; i < temperatures.size(); i++) {
        while (!stack.empty() && temperatures[i] > temperatures[stack.back()]) {
            int j = stack.back();
            stack.pop_back();
            res[j] = i - j;
        }
        stack.push_back(i);
    }
    return res;
}

Java

public int[] dailyTemperatures(int[] temperatures) {
    Deque<Integer> stack = new ArrayDeque<>();  // indices; decreasing stack
    int[] res = new int[temperatures.length];
    for (int i = 0; i < temperatures.length; i++) {
        while (!stack.isEmpty() && temperatures[i] > temperatures[stack.peek()]) {
            int j = stack.pop();
            res[j] = i - j;
        }
        stack.push(i);
    }
    return res;
}

Example: Monotonic increasing — Next Smaller Element

For each element, find the next smaller element to the right (or -1 / sentinel). Use an increasing stack (by value). When the current value is less than the value at the index on top, the current value is the next smaller for that index; pop and record, then push current index.

A: [4, 5, 2, 10, 8, 7]
    0  1  2   3  4  5

i=0: stack=[0]
i=1: 5≥4 → stack=[0,1]
i=2: 2<5 → pop 1, nse[1]=2; 2<4 → pop 0, nse[0]=2; stack=[2]
i=3: 10≥2 → stack=[2,3]
i=4: 8<10 → pop 3, nse[3]=4; 8≥2 → stack=[2,4]
i=5: 7<8 → pop 4, nse[4]=5; 7≥2 → stack=[2,5]
nse = [2, 2, -1, 4, 5, -1]  (index or -1)

Python

def next_smaller_element(nums: list[int]) -> list[int]:
    stack: list[int] = []  # indices; increasing stack (bottom to top)
    nse = [-1] * len(nums)
    for i, x in enumerate(nums):
        while stack and x < nums[stack[-1]]:
            j = stack.pop()
            nse[j] = i  # or nse[j] = x for value
        stack.append(i)
    return nse

C++

vector<int> nextSmallerElement(vector<int>& nums) {
    vector<int> stack;
    vector<int> nse(nums.size(), -1);
    for (int i = 0; i < nums.size(); i++) {
        while (!stack.empty() && nums[i] < nums[stack.back()]) {
            nse[stack.back()] = i;
            stack.pop_back();
        }
        stack.push_back(i);
    }
    return nse;
}

Java

public int[] nextSmallerElement(int[] nums) {
    Deque<Integer> stack = new ArrayDeque<>();
    int[] nse = new int[nums.length];
    Arrays.fill(nse, -1);
    for (int i = 0; i < nums.length; i++) {
        while (!stack.isEmpty() && nums[i] < nums[stack.peek()]) {
            nse[stack.pop()] = i;
        }
        stack.push(i);
    }
    return nse;
}

Quick reference

Pattern identification

Pattern	Description	Example Problem	Category
Next/Previous Greater	For each element, find first greater on left or right	Next Greater Element, Daily Temperatures, Stock Span	Decreasing stack
Next/Previous Smaller	For each element, find first smaller on left or right	Next Smaller Element, Largest Rectangle in Histogram	Increasing stack
Spans / ranges	Bounds where current is min/max in a range	Stock Span, Largest Rectangle, Sum of Subarray Minimums	Both
Sliding window / subarray	Min/max over subarrays or contribution to sum	Sum of Subarray Minimums, Sum of Subarray Maximums	Both
Others	Trapping Rain Water, Remove K Digits, circular NGE	Trapping Rain Water, Remove K Digits	Both

Implementation reference

Stack type	Order (bottom → top)	When to pop	Mapping on pop	Complexity
Decreasing	High → low	Current value > stack top’s value	Popped index’s next greater = current	O(n)
Increasing	Low → high	Current value < stack top’s value	Popped index’s next smaller = current	O(n)