Monotonic Stack Pattern: Solve Next Greater Element in O(n)

Imagine you have an array of stock prices and you need to find, for each day, the next day with a higher price. The brute-force approach uses nested loops — for every element, scan right until you find something larger. That is O(n^2), and it crumbles on large inputs.

The monotonic stack leetcode pattern solves this entire class of problems in O(n) time and O(n) space. It is one of the most elegant optimizations you will encounter, and once you see it, you will recognize it everywhere.

The core insight is simple: instead of scanning forward from each element, you process elements left to right and use a stack to remember "unresolved" elements that are still waiting for their answer. When a new element arrives that resolves one or more waiting elements, you pop them off and record the answer.

This pattern appears across dozens of LeetCode problems and is a go-to topic for interviewers at companies like Google, Amazon, and Meta. Mastering it gives you a reliable O(n) template you can apply to at least five to ten common interview questions.

A monotonic stack is a stack whose elements are always in sorted order — either strictly increasing from bottom to top, or strictly decreasing from bottom to top. The "monotonic" part means the order never reverses.

When you push a new element, you first pop everything that would violate the ordering invariant. Those popped elements have just found their "answer" — the new element is the one they were waiting for.

There are two flavors. A decreasing monotonic stack keeps elements in decreasing order from bottom to top. When a larger element arrives, smaller elements get popped — which means the larger element is the "next greater element" for each popped item. An increasing monotonic stack is the mirror image: it keeps elements in increasing order, and a smaller arriving element triggers pops.

The key to understanding monotonic stacks is that each element is pushed exactly once and popped at most once. That means the total number of push and pop operations across the entire array is O(n), giving you linear time regardless of how many pops happen on any single iteration.

The decreasing monotonic stack is the most common variant. It solves the classic "next greater element" problem: for each element in the array, find the first element to its right that is strictly larger.

Here is the template in plain English. Initialize an empty stack and a result array filled with -1 (meaning "no greater element found"). Iterate through the array from left to right. For each element, while the stack is not empty and the current element is greater than the element at the index on top of the stack, pop the stack and set result[popped index] to the current element. Then push the current index onto the stack.

After processing the entire array, any indices still on the stack have no next greater element — their result stays -1. The stack maintained a decreasing order throughout, and every violation of that order triggered an answer.

This exact template solves Next Greater Element I (LeetCode #496), Next Greater Element II (#503, with a circular array twist), and Daily Temperatures (#739, where you return distances instead of values). The only thing that changes between these problems is what you record when you pop.

The increasing monotonic stack is the mirror image. It maintains elements in increasing order from bottom to top, and pops when a smaller element arrives. This solves "next smaller element" problems.

The template is identical to the decreasing version with one change: the pop condition flips. While the stack is not empty and the current element is less than the element at the stack top index, pop and record the answer.

You see the increasing stack in problems like Stock Span (#901) and in subproblems within Largest Rectangle in Histogram (#84). In the stock span problem, you need to find how many consecutive days before today had a price less than or equal to today — which is essentially finding the "previous greater element."

Some problems require both directions. Largest Rectangle in Histogram needs you to find, for each bar, the nearest shorter bar to the left and the nearest shorter bar to the right. You can run two passes (one forward, one backward) or use a single pass with careful handling of the remaining stack elements. Either way, the monotonic stack is the engine.

Once you learn the monotonic stack template, a handful of classic problems become straightforward. Here are the ones you should know for interviews.

Next Greater Element I (#496) is the purest application. You are given two arrays, and for each element in the first array, you find its next greater element in the second array. Build a hash map from the monotonic stack pass on the second array, then look up answers for the first array. This is the problem to solve first when learning the pattern.

Daily Temperatures (#739) asks: for each day, how many days until a warmer temperature? This is next-greater-element with indices — when you pop, record the distance (current index minus popped index) instead of the value. It is the most commonly asked monotonic stack problem in interviews.

Largest Rectangle in Histogram (#84) is the hardest standard monotonic stack problem. For each bar, you need the nearest shorter bar on each side to compute the maximal rectangle. This problem combines increasing stack concepts with careful width calculations and is frequently asked at Google and Amazon.

Trapping Rain Water (#42) can be solved with a stack approach. As you iterate, you maintain a decreasing stack of bar heights. When a taller bar arrives, you pop and compute the trapped water between the current bar and the new stack top. This is one of three common approaches to the problem (the others being two pointers and prefix max arrays).

Stock Span Problem (#901) asks for the number of consecutive days with price less than or equal to today. This is a "previous greater element" problem. Maintain a decreasing stack of prices (or indices), and when you push today, pop all smaller prices — the span is the distance from today to the new stack top.

Recognizing that a problem needs a monotonic stack is half the battle. Here are the trigger phrases and patterns to watch for in problem statements.

The most obvious signal is the phrase "next greater element" or "next smaller element." If the problem explicitly asks for the nearest element that is larger or smaller, you almost certainly need a monotonic stack.

Less obvious signals include the words "span" (as in stock span), "rectangle" (as in histogram), and any problem that asks about relationships between each element and its nearest neighbor with some property. If you see "for each element, find the first element to the right/left that is greater/smaller," that is a monotonic stack.

The biggest red flag for recognizing a monotonic stack opportunity is when your brute-force solution uses nested loops where the inner loop searches for the next bigger or smaller element. That nested loop pattern is O(n^2), and the monotonic stack converts it to O(n) by processing each element exactly twice — once on push, once on pop.

The monotonic stack pattern has a clear learning progression. Start with Daily Temperatures (#739) because it is the most intuitive — you can visualize temperatures rising and falling, and the stack logic maps directly to the problem. Solve it yourself before reading solutions.

Next, tackle Next Greater Element I (#496) and its circular variant Next Greater Element II (#503). These reinforce the core template and introduce the trick of iterating through the array twice for circular problems.

Once the basic template feels natural, move to Largest Rectangle in Histogram (#84). This is where the pattern gets challenging because you need to compute widths from stack indices and handle the cleanup of remaining stack elements. Take your time with this one — it is a common interview problem and worth understanding deeply.

Finally, try Trapping Rain Water (#42) with the stack approach and Stock Span (#901) to see variations of the pattern. By this point, you should be able to recognize a monotonic stack problem within the first few minutes of reading a problem statement.

Use YeetCode flashcards to drill the monotonic stack template and the key recognition signals. Spaced repetition is especially effective for pattern-based problems because the template is the same across many problems — you just need to recall the right variant and the specific twist for each problem.