Monotonic Stack Pattern Fixes O(n²) Stock Indexing

Most developers hit a wall with array problems that demand knowing the 'next greater' or 'previous smaller' element at every index. The naive approach — a nested loop — works on paper but collapses at scale. When you're processing stock prices, rendering bar charts, or evaluating weather forecasts over millions of data points, O(n²) isn't a trade-off; it's a dealbreaker. The monotonic stack pattern is one of those rare tools that turns a quadratic problem into a linear one without any exotic data structure magic — just a regular stack used with discipline.

The core problem it solves is deceptively simple: for each element in an array, find the nearest element to its left or right that is greater or smaller than it. Brute force checks every pair. The monotonic stack makes one observation that changes everything — if you're scanning left-to-right and you encounter an element that 'dominates' the element on top of the stack, the dominated element has found its answer. You process it, pop it, and never look at it again. That amortized O(1) pop-per-element is where the O(n) total time comes from.

By the end of this article you'll be able to implement both monotonically increasing and decreasing stacks from scratch, identify which variant a problem requires, handle tricky edge cases like duplicate values and circular arrays, and explain the amortized time complexity to an interviewer without flinching. You'll also walk away with a mental checklist that maps problem phrasing directly to the right stack orientation — so you stop guessing.

How a Stack Becomes Monotonic and Why That Cuts O(n²) to O(n)

A monotonic stack is a stack whose elements remain in strictly increasing or decreasing order as you push new items. The core mechanic: before pushing a new element, pop all elements that violate the desired order. This single pass over the input, with each element pushed and popped at most once, yields O(n) total time — a direct replacement for nested loops that would cost O(n²).

In practice, you maintain either a monotonic increasing stack (for next smaller element) or monotonic decreasing stack (for next greater element). The key property: when you pop an element, you know the current incoming element is the first element that breaks the monotonic condition for the popped element. This gives you an immediate answer for that popped element's "next" relationship without revisiting it. The stack holds indices, not values, so you can compute distances or retrieve values from the original array.

Use this pattern whenever you need to find the next (or previous) greater or smaller element for every position in an array — stock span, daily temperatures, histogram largest rectangle, or sliding window maximum. In real systems, this replaces O(n²) brute-force indexing with a single linear pass, which matters when processing millions of price ticks or sensor readings per second.

How Monotonic Stack Works — Step by Step

Let's build a monotonic decreasing stack to find the next greater element (NGE) for each index. The stack maintains indices of elements in decreasing order of their values (biggest on top? No — actually, decreasing stack means values decrease from bottom to top). Here's the algorithm:

1. Initialize an empty stack.
2. For each index i from 0 to n-1:
3. - While stack is not empty AND arr[stack.top] < arr[i]:
4. pop top index j → record result[j] = arr[i]
5. - Push i onto stack.
6. Any indices still in stack have no rightward greater elements → their result stays -1.

For an increasing stack (next smaller element), flip the condition to arr[stack.top] > arr[i].

Key insight: the popped element's answer is the current element. This is a one‑pass algorithm.

Worked Example — Tracing the Algorithm

Find next greater element for [4, 5, 2, 10, 8].

i=0 (4): stack empty. Push 0. stack=[0]. i=1 (5): arr[0]=4 < 5. Pop 0. result[0]=5. Stack empty. Push 1. stack=[1]. i=2 (2): arr[1]=5 >= 2. Push 2. stack=[1,2]. i=3 (10): arr[2]=2 < 10. Pop 2. result[2]=10. arr[1]=5 < 10. Pop 1. result[1]=10. Stack empty. Push 3. stack=[3]. i=4 (8): arr[3]=10 >= 8. Push 4. stack=[3,4]. End: stack has [3,4] remaining. result[3]=-1, result[4]=-1.

Result: [5, 10, 10, -1, -1]

def next_greater_element(arr):
    n = len(arr)
    result = [-1] * n
    stack  = []
    for i in range(n):
        while stack and arr[stack[-1]] < arr[i]:
            j = stack.pop()
            result[j] = arr[i]
        stack.append(i)
    return result

print(next_greater_element([4, 5, 2, 10, 8]))

Implementation — Python and Java

Below are clean implementations in Python and Java. The pattern is identical across languages: a stack of indices, a while loop with the monotonic condition, and a final sweep for unpopped indices.

Important: always store indices in the stack, not values. You need the index to fill the result array. The value is retrieved via arr[stack.top].

def next_greater_element(arr):
    result = [-1] * len(arr)
    stack = []
    for i in range(len(arr)):
        while stack and arr[stack[-1]] < arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    return result

def next_smaller_element(arr):
    result = [-1] * len(arr)
    stack = []
    for i in range(len(arr)):
        while stack and arr[stack[-1]] > arr[i]:
            idx = stack.pop()
            result[idx] = arr[i]
        stack.append(i)
    return result

Real‑World Use Cases — Beyond the Basics

The monotonic stack isn't just an interview trick. It appears in production code for:

• Largest Rectangle in Histogram: For each bar, the area is height * (right_smaller - left_smaller - 1). Monotonic increasing stack finds both boundaries in one pass.
• Trapping Rain Water: Maintain stack of decreasing heights; when a taller bar arrives, compute water trapped above the popped bar.
• Stock Span Problem: For each day, find how many consecutive days before today the price was ≤ today's. Monotonic decreasing stack with indices.

Each of these uses the same core pattern with a small twist.

Complexity Analysis — Why O(n) Amortised

Each element is pushed onto the stack exactly once. Each element can be popped at most once. Total number of push/pop operations is therefore ≤ 2n. The inner while loop may run many times for a single outer iteration, but across the entire run, the total pops equal the number of pushes. This gives an amortised O(1) per element. Space is O(n) for the stack in the worst case (e.g., decreasing array for next greater).

Formally: each iteration of the while loop pops an element, and each element is popped at most once → O(n) total while iterations.

What A Monotonic Stack Actually Is — And Isn't

A monotonic stack is just a stack that enforces a single rule: every new element must maintain the stack's sorted order before you push it. If that means popping elements that break the order, you pop. That's it. There's no magic. No hidden complexity.

Why does this matter? Because that forced ordering lets you answer one question instantly: "What was the last element that was larger (or smaller) than the current one?" That's the root of every nearest-greater/smaller-element problem. When you pop an element, you know exactly which incoming element dominated it. That relationship is the key to collapsing O(n²) brute-force scans into O(n) amortised time.

Most tutorials fluff this up with diagrams and multiple examples. Here's the raw truth: monotonic stacks are a specific tool for a narrow set of problems — finding the next/previous greater/smaller element. If you don't need that relationship, don't touch this pattern.

// io.thecodeforge — dsa tutorial

// Minimal monotonic increasing stack — finds next smaller element
import java.util.ArrayDeque;
import java.util.Deque;

public class MonotonicStackEssence {
    public static int[] nextSmallerElement(int[] prices) {
        int[] result = new int[prices.length];
        Deque<Integer> stack = new ArrayDeque<>();
        
        // Traverse right-to-left to find next smaller element
        for (int i = prices.length - 1; i >= 0; i--) {
            while (!stack.isEmpty() && stack.peek() >= prices[i]) {
                stack.pop();
            }
            result[i] = stack.isEmpty() ? -1 : stack.peek();
            stack.push(prices[i]);
        }
        return result;
    }

    public static void main(String[] args) {
        int[] prices = {8, 4, 6, 2, 3};
        int[] nextSmaller = nextSmallerElement(prices);
        for (int val : nextSmaller) {
            System.out.print(val + " ");
        }
        System.out.println();
    }
}

How To Spot A Monotonic Stack Problem Instantly

Stop memorising problem titles. Look for the pattern in the language. If the problem says "nearest element that is greater/smaller to the left/right" — that's your signal. No other technique gives you that relationship in O(n).

But here's where juniors get lost: the problem won't always say "nearest greater element". It'll say "stock span" or "trapping rain water" or "largest rectangle in histogram". Those are camouflage. The core mechanic is still: for each element, find the first element to its left or right that's larger or smaller. Learn to see through the disguise.

Three questions to ask yourself in any array problem: 1. Does the answer for each element depend on the first larger/smaller neighbour? 2. Can I process elements left-to-right or right-to-left in a single pass? 3. Does the naive O(n²) solution involve checking each element against every neighbour?

If you answered yes to at least two of those, a monotonic stack is your weapon.

// io.thecodeforge — dsa tutorial

// Online stock span — classic monotonic stack disguise
import java.util.ArrayDeque;
import java.util.Deque;

public class StockSpanDetection {
    static class StockSpanner {
        record Day(int price, int span) {}
        private Deque<Day> monotonicStack = new ArrayDeque<>();
        
        public int next(int price) {
            int span = 1;
            // Pop while stack top is <= current price
            while (!monotonicStack.isEmpty() && 
                   monotonicStack.peek().price() <= price) {
                span += monotonicStack.pop().span();
            }
            monotonicStack.push(new Day(price, span));
            return span;
        }
    }

    public static void main(String[] args) {
        StockSpanner spanner = new StockSpanner();
        int[] prices = {100, 80, 60, 70, 60, 75, 85};
        for (int p : prices) {
            System.out.print(spanner.next(p) + " ");
        }
        System.out.println();
    }
}

Conclusion

The monotonic stack pattern fundamentally reshapes how you approach subarray and subsequence problems by trading excess comparison work for a single-pass, ordered stack. Instead of checking every element against every other element in O(n²) time, the monotonic property ensures that each element enters and leaves the stack exactly once, achieving O(n) amortised runtime. This efficiency comes from encoding dependency relationships — next greater element, nearest smaller value, or maximum width of a histogram — into stack invariants. The pattern is not magic; it is just a disciplined application of stack discipline combined with a monotonic invariant. When you see a problem asking for the next larger element, the maximum area under a histogram, or the longest valid subarray with a monotonic constraint, ask yourself: can I derive this answer from a monotonic stack? If yes, implement a while loop that pops while the invariant breaks, then push the current index. The hardest part is deciding whether the stack should increase or decrease, and that decision hinges on whether you need the next greater or next smaller element. Once you internalise that, the monotonic stack becomes one of the most reliable tools in your DSA toolkit.

// io.thecodeforge — dsa tutorial
// Example: next greater element (monotonic decreasing stack)
import java.util.*;
class MonotonicStackConclusion {
    public int[] nextGreaterElement(int[] nums) {
        int n = nums.length;
        int[] result = new int[n];
        Arrays.fill(result, -1);
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < n; i++) {
            while (!stack.isEmpty() && nums[stack.peek()] < nums[i]) {
                int idx = stack.pop();
                result[idx] = nums[i];
            }
            stack.push(i);
        }
        return result;
    }
}

What A Monotonic Stack Actually Is — And Isn't

A monotonic stack is a stack whose elements are arranged in either strictly increasing or strictly decreasing order from bottom to top. It is not a separate data structure — it is a disciplined usage pattern of a standard stack. When you push a new element, you first pop all elements that violate the monotonic order, then push. The key insight is that the stack never holds elements out of order; it enforces a sorted traversal of indices, not values. This is not a priority queue, because the order is based on value magnitude, not priority; and it is not a sorted array, because the stack only holds a subset of elements at any time. When people misuse the term, they often confuse it with a monotonic queue (used for sliding window maximum) which dequeues from both ends. The monotonic stack is strictly LIFO with a value constraint. Its power comes from the fact that when an element is popped, you know it is the first time a violating element appears to its right (or left, depending on traversal direction). That immediate contextual knowledge is what enables O(n) solutions for problems like largest rectangle in histogram or trapping rain water — it is not a catch-all for every subarray problem, only those where the answer depends on the nearest violating neighbour.

// io.thecodeforge — dsa tutorial
// Demonstrate monotonic stack v.s. sorted stack
import java.util.*;
class WhatMonotonicStackIs {
    public static void main(String[] args) {
        int[] arr = {3, 1, 4, 2};
        Deque<Integer> monoStack = new ArrayDeque<>();
        for (int val : arr) {
            while (!monoStack.isEmpty() && monoStack.peek() > val) {
                monoStack.pop(); // maintain increasing order
            }
            monoStack.push(val);
        }
        // monoStack bottom-to-top: 1,2 (not 3,1,4,2)
        System.out.println(monoStack);
    }
}