Skills101

AdvancedData Structures & Algorithms · Lesson 23 of 25 · Updated ·

Monotonic Stack — Next Greater Element, Stock Span and Histograms in O(n)

Many array problems ask, for every element: "what is the next bigger value to my right?" (or the previous smaller one, or how far away it is). Checking every pair is O(n²). A monotonic stack — a stack whose values are always kept in increasing or decreasing order — answers all of them in one pass, O(n).

1. Next greater element

Problem: for each element, print the first value to its right that is strictly greater, or -1 if there is none.

Idea: walk left to right and keep a stack of elements that are still waiting for their next greater value. When a new value x arrives, it is the answer for every waiting element smaller than it — pop them all. Then x waits too.

For the array 2 1 4 3 6 5 the next greater elements are 4 4 6 6 -1 -1; arrows go from 2 and 1 to 4, and from 4 and 3 to 6

The waiting elements always form a decreasing stack — anything smaller than a newer element would already have been popped.

Stack after each step: see 2 gives [2]; see 1 gives [2, 1]; see 4 pops 1 and 2 and gives [4]; see 3 gives [4, 3]; see 6 pops 3 and 4 and gives [6]; see 5 gives [6, 5]

def next_greater(a):
    ans = [-1] * len(a)
    stack = []                       # indexes still waiting for an answer
    for i, x in enumerate(a):
        while stack and a[stack[-1]] < x:
            ans[stack.pop()] = x     # x is the next greater for that index
        stack.append(i)
    return ans

print(next_greater([2, 1, 4, 3, 6, 5]))
print(next_greater([5, 4, 3]))
[4, 4, 6, 6, -1, -1]
[-1, -1, -1]

Why O(n)? Each index is pushed once and popped at most once, so the inner while runs at most n times in total — even though it is inside a for.

Store indexes, not values. With the index you can return the value, the distance (i − j) or the position — whatever the problem asks.

2. The four variants

Change two things — the comparison and the direction — and the same loop solves four problems:

You wantWalkPop while the top is…The stack is
next greaterleft → rightsmaller than xdecreasing
next smallerleft → rightgreater than xincreasing
previous greaterleft → right≤ x, then the top is the answerdecreasing
previous smallerleft → right≥ x, then the top is the answerincreasing

For the "previous" versions, the answer for x is whatever is left on top after popping.

def previous_smaller(a):
    ans, stack = [], []
    for x in a:
        while stack and stack[-1] >= x:
            stack.pop()
        ans.append(stack[-1] if stack else -1)
        stack.append(x)
    return ans

print(previous_smaller([4, 5, 2, 10, 8]))
[-1, 4, -1, 2, 2]

3. Daily temperatures (distance to the next warmer day)

"For each day, how many days until a warmer one? 0 if never." Same loop; store the distance.

def daily_temperatures(t):
    ans, stack = [0] * len(t), []
    for i, x in enumerate(t):
        while stack and t[stack[-1]] < x:
            j = stack.pop()
            ans[j] = i - j
        stack.append(i)
    return ans

print(daily_temperatures([73, 74, 75, 71, 69, 72, 76, 73]))
[1, 1, 4, 2, 1, 1, 0, 0]

4. Largest rectangle in a histogram

The hardest classic. Each bar can be the shortest bar of a rectangle that stretches left and right until a shorter bar blocks it. So for each bar we need its previous smaller and next smaller bar — one increasing stack finds both: when a bar is popped, the bar that pops it is its next smaller, and the bar below it on the stack is its previous smaller.

def largest_rectangle(h):
    stack, best = [], 0               # indexes, heights increasing
    for i, x in enumerate(h + [0]):   # a final 0 pops everything left
        while stack and h[stack[-1]] > x:
            height = h[stack.pop()]
            left = stack[-1] + 1 if stack else 0
            best = max(best, height * (i - left))
        stack.append(i)
    return best

print(largest_rectangle([2, 1, 5, 6, 2, 3]))
print(largest_rectangle([2, 4]))
10
4

The answer 10 is the rectangle of height 5 over the bars 5, 6. The sentinel 0 at the end makes sure every bar is popped and measured.

Next greater element in Java

import java.util.*;

public class Main {
    static int[] nextGreater(int[] a) {
        int[] ans = new int[a.length];
        Arrays.fill(ans, -1);
        Deque<Integer> stack = new ArrayDeque<>();   // use ArrayDeque, not the old Stack class
        for (int i = 0; i < a.length; i++) {
            while (!stack.isEmpty() && a[stack.peek()] < a[i]) {
                ans[stack.pop()] = a[i];
            }
            stack.push(i);
        }
        return ans;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(nextGreater(new int[]{2, 1, 4, 3, 6, 5})));
    }
}
[4, 4, 6, 6, -1, -1]

5. How to spot a monotonic stack problem

  • The words next / previous greater / smaller, "how many days until", "span", "visible", "nearest taller".
  • A brute force with a nested loop that scans left or right until it finds something bigger or smaller.
  • Circular arrays (next greater element II): loop over the array twice (i % n), pushing only during the first pass.

Common mistakes

  • Pushing values when you later need positions or distances — push indexes.
  • Using <= instead of < (or the other way round): it decides whether equal values count as "greater". Read the problem.
  • Forgetting the sentinel (or a final clean-up loop) in the histogram problem, so bars left on the stack are never measured.
  • Thinking the nested while makes it O(n²) — it doesn't; count pushes and pops.

Quick recap

  • A monotonic stack keeps values in order; elements wait on it until their answer arrives.
  • Next greater: pop while the top is smaller than x; each popped index gets x.
  • Every index is pushed and popped at most once: O(n) time, O(n) space.
  • Same pattern: next/previous smaller, daily temperatures, stock span, largest rectangle.

Practice what you learned

📝 Quiz: Monotonic Stack5 questions · instant answers & explanations · +10 XP · counts towards your free certificateTake the quiz →