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.

What is Monotonic Stack? — Plain English

A monotonic stack maintains elements in either strictly increasing or strictly decreasing order. When a new element is pushed, any elements on the stack that violate the monotonic property are popped first. The moment an element is popped because of a new incoming element, that defines a relationship — typically 'the next greater element' or 'the next smaller element'.

Monotonic stacks solve in O(n) problems that naively take O(n^2): next greater element, previous smaller element, largest rectangle in histogram, trapped rainwater.

This section sets the foundation. You'll see the pattern re‑occur in dozens of interview and production problems.

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.

Frequently Asked Questions