Monotonic Stack Pattern

Why this pattern matters for LeetCode

The brute force for 'next greater element' checks everything to the right for each position — O(n²). A monotonic stack solves this in one O(n) pass. The key insight: maintain a stack of 'unresolved' indexes. When a new element breaks the stack's order (is greater than the top), the top's question is finally answered — pop it, record the gap, and repeat until the order holds. Push the new index. Each element is pushed once and popped at most once — O(n) total operations.

What the Monotonic Stack pattern is

A monotonic stack maintains elements in strictly increasing or strictly decreasing order. When a new element would violate that order, you pop until the order is restored — and the pop is where the work happens. For 'next greater element' problems, maintain a decreasing stack of unresolved indexes. When you encounter a larger element, everything it's greater than gets its answer at that moment. For histogram problems, maintain an increasing stack of heights and pop when a shorter bar arrives to compute the maximum rectangle.

Reach for Monotonic Stack when you catch yourself thinking…

These are the internal questions that signal this pattern.

Beginner mental model

When to use Monotonic Stack

• ✓Finding the next greater (or smaller) element for each position in an array
• ✓Computing how many days until a warmer temperature (Daily Temperatures)
• ✓Finding the largest rectangle in a histogram — pop when a shorter bar arrives
• ✓Calculating spans — how many consecutive prior days a value was at or below today's
• ✓Any problem where each element's answer is the first future element that breaks a pattern

When NOT to use Monotonic Stack

• ✕You only need the global maximum or minimum — a simple variable scan is faster and simpler
• ✕The problem compares values at two specific positions, not 'next' relationships — Two Pointers may apply
• ✕You need the maximum within a sliding window of fixed size — use a monotonic deque instead
• ✕The condition involves non-adjacent elements with no directional 'next' relationship

Better alternative: In those cases, a simple linear scan (for global max/min) or a monotonic deque (for sliding window max/min) is more appropriate.

JavaScript code template

Daily Temperatures — O(n) time, O(n) space

function dailyTemperatures(temperatures) {
  const result = new Array(temperatures.length).fill(0);
  const stack = []; // stores unresolved indexes

  for (let i = 0; i < temperatures.length; i++) {
    // While current temp is warmer than the day at the top of the stack
    while (stack.length && temperatures[i] > temperatures[stack[stack.length - 1]]) {
      const idx = stack.pop();
      result[idx] = i - idx; // days waited = current index minus popped index
    }
    stack.push(i); // unresolved — push this day's index
  }

  return result; // indexes still in stack have no warmer future day (stays 0)
}

The stack holds indexes of days whose 'next warmer day' is still unknown, in decreasing temperature order. For each new day, compare its temperature to the day at the top of the stack. If it's warmer, the top's question is answered — pop it and record the gap. Keep popping until the top is warmer than today or the stack is empty. Then push today's index. Any indexes remaining at the end had no warmer future day and their result stays 0.

Step-by-step thinking process

Walk through this in your head before writing code.

1. 1Create a result array filled with the default value (0 or -1) and an empty stack.
2. 2Loop through the array from left to right.
3. 3While the stack is not empty and the current element breaks the monotonic order, pop the top index.
4. 4For the popped index, record its answer — typically the gap between the current index and the popped index.
5. 5Push the current index onto the stack (it's now an unresolved question).
6. 6After the loop, indexes still in the stack have no valid answer — leave them at the default.

LeetCode-style problems that use this pattern

Practice on DSA Trainer with guided hints: no spoilers, just nudges.

• Daily Temperatures

  Push unresolved indexes. When a warmer day arrives, pop and record the gap — the textbook monotonic stack problem.

  Premium→
• Next Greater Element I

  Build a monotonic stack on nums2 to precompute each element's next greater value, then look up each element of nums1.

  Premium→
• Next Greater Element II

  Circular array — loop through twice (or use index mod n) so every element sees the elements that wrap around after it.

  Premium→
• Largest Rectangle in Histogram

  Monotonic increasing stack — pop when a shorter bar arrives and compute the rectangle width using the gap between the current index and the new top.

  Premium→
• Stock Spanner

  Each day's span is how many consecutive prior days had a price at or below today's. Maintain a decreasing stack of (price, span) pairs.

  Premium→

Common mistakes beginners make

• ✕Storing values instead of indexes — you need the index to compute the gap (i - stack[top]) and to write to the result array at the correct position.
• ✕Popping without recording the answer — the pop is where the result is computed and stored. Don't pop silently.
• ✕Confusing a plain stack with a monotonic stack — a plain stack tracks nesting (brackets); a monotonic stack tracks unresolved 'next' relationships, maintained in sorted order.
• ✕Using a decreasing stack when you need an increasing one — decreasing stacks answer 'next greater element'; increasing stacks answer 'next smaller element.'

Monotonic Stack vs Plain Stack vs Sliding Window Deque

Choose the right tool for the job.

Time and space complexity

Each element is pushed onto the stack exactly once and popped at most once. Both operations are O(1), so across n elements the total work is O(n). The stack holds at most n indexes at once in the worst case (a strictly decreasing array where no element is ever popped) — O(n) space.

Frequently asked questions

When do I use a decreasing vs increasing monotonic stack?

A decreasing stack (each element is smaller than the one below) answers 'next greater element' questions — the order is violated by something larger, which is the answer. An increasing stack (each element is larger) answers 'next smaller element' questions. Think about what order is violated when you find the answer you're looking for.

Why store indexes instead of values on the stack?

You need the index for two reasons: to compute the gap (current index minus popped index gives days waited) and to write the result at the correct position in the output array. Store indexes on the stack, then access the value with temperatures[stack[stack.length - 1]] when you need to compare.

What's the difference between a monotonic stack and a plain stack?

A plain stack just stores things in LIFO order — bracket matching and nesting problems use it without caring about the relative ordering of elements. A monotonic stack enforces a strict ordering invariant as it goes, and the moment that invariant is violated, you pop and record an answer. The ordering is the mechanism that gives you 'next greater/smaller' in O(n).

What happens to indexes still in the stack after the loop?

They have no valid answer — no future element ever broke the monotonic order for them. For Daily Temperatures, their result stays 0 (no warmer future day). For Next Greater Element, their result is -1. The default fill before the loop handles this — you never need to explicitly process the remaining stack.