Monotonic Stack Explained: Next Greater Element, Daily Temperatures and Largest Rectangle in Histogram

Given an array, find for every element the next larger value to its right. Scanning forward from each position works but takes O(n²), and it times out on big inputs. A monotonic stack does it in one pass. Once the idea clicks, Daily Temperatures, Stock Span and even Largest Rectangle in Histogram look like the same problem. We build it from scratch, trace each solution by hand and end with a reusable template. All code was run against test cases.

What is a monotonic stack?

A normal stack lets you push and pop at the top. A monotonic stack adds one rule: the values inside the stack must always stay in sorted order, either increasing or decreasing from bottom to top. Before you push a new element, you pop every element from the top that would break that order. That tiny rule is what makes the stack useful.

The popped elements are not wasted. Each time an element is popped, you have just learned something about it: the new element that forced it out is the first one that is bigger (or smaller) than it. In other words, a pop is the moment an element finds its answer.

Why is it O(n) and not O(n²)?

The code contains a while loop inside a for loop, so it looks quadratic. It is not. Every index is pushed onto the stack exactly once and popped at most once. Across the whole run there are at most n pushes and n pops, so the total work is at most 2n steps. The inner loop is only expensive when it pops many elements, and those elements can never be popped again. This is the same amortised argument we used for the sliding window pattern.

Increasing or decreasing stack?

A useful way to remember it: to find larger values, keep the stack decreasing, because a bigger value arriving is exactly what removes the smaller ones waiting below it.

Problem 1: Next Greater Element

For each number in an array, find the first number to its right that is larger. If there is none, the answer is -1.

def next_greater(nums):
    res = [-1] * len(nums)
    stack = []                      # indices, values decreasing
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] < n:
            res[stack.pop()] = n    # n is the answer for the popped index
        stack.append(i)
    return res

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

Trace on [2, 1, 2, 4, 3]

1. i = 0, value 2. The stack is empty, so push index 0. Stack: [0].
2. i = 1, value 1. The top value is 2, which is not smaller than 1, so push. Stack: [0, 1].
3. i = 2, value 2. The top value 1 is smaller than 2, so pop index 1 and record 2 as its answer. The next top value 2 is not smaller than 2, so stop and push. Stack: [0, 2].
4. i = 3, value 4. Value 2 at index 2 is smaller, so its answer is 4. Value 2 at index 0 is also smaller, so its answer is 4 as well. Push. Stack: [3].
5. i = 4, value 3. The top value 4 is larger, so push. Stack: [3, 4].

The indices still left on the stack, 3 and 4, never found a larger value, so they keep the default -1. The final answer is [4, 2, 4, -1, -1]. We store indices instead of values because many problems need the position, and the value is always one lookup away.

Problem 2: Daily Temperatures

Given daily temperatures, return for each day how many days you must wait for a warmer one, or 0 if there is none. This is Next Greater Element, except we return the distance instead of the value.

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

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

On day 5 the temperature 72 arrives. It is warmer than 69 (day 4) and 71 (day 3), so those two days get answers 1 and 2. It is not warmer than 75, so day 2 keeps waiting. On day 6 the temperature 76 is warmer than 72 and 75, giving days 5 and 2 answers of 1 and 4. Days 6 and 7 never see a warmer day, so they stay at 0. Time is O(n) and extra space is O(n).

Problem 3: Next Smaller Element

Flip the comparison and you flip the problem. Use an increasing stack, and pop while the new value is smaller than the top.

def next_smaller(nums):
    res = [-1] * len(nums)
    stack = []
    for i, n in enumerate(nums):
        while stack and nums[stack[-1]] > n:
            res[stack.pop()] = n
        stack.append(i)
    return res

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

Problem 4: circular arrays

In Next Greater Element II the array is circular, so after the last element the search wraps around to the first. The trick is to loop over the array twice, using i % n to read values, and only push indices during the first pass.

def next_greater_circular(nums):
    n = len(nums)
    res = [-1] * n
    stack = []
    for i in range(2 * n):
        x = nums[i % n]
        while stack and nums[stack[-1]] < x:
            res[stack.pop()] = x
        if i < n:
            stack.append(i)
    return res

print(next_greater_circular([1, 2, 1]))   # [2, -1, 2]

The last 1 finds the 2 at the start of the array by wrapping around. The 2 is the maximum, so it keeps -1. The complexity is still O(n), because the stack handles at most 2n elements.

Problem 5: Online Stock Span

The span of today’s price is the number of consecutive days, ending today, with a price less than or equal to today’s. This asks about the previous greater element, and a neat version stores a price together with its span.

class StockSpanner:
    def __init__(self):
        self.stack = []             # (price, span), prices decreasing

    def next(self, price):
        span = 1
        while self.stack and self.stack[-1][0] <= price:
            span += self.stack.pop()[1]
        self.stack.append((price, span))
        return span

s = StockSpanner()
print([s.next(p) for p in [100, 80, 60, 70, 60, 75, 85]])
# [1, 1, 1, 2, 1, 4, 6]

When 75 arrives, it absorbs the spans of 60 and 70 (1 + 2), so its span is 1 + 1 + 2 = 4. When 85 arrives, it absorbs 75 (span 4) and 80 (span 1), giving 6.

Problem 6: Largest Rectangle in Histogram

This is the classic harder problem. Given bar heights, find the area of the largest rectangle. For every bar, the widest rectangle using that bar as its height stretches left and right until it meets a shorter bar. So for each bar we need the previous smaller and the next smaller position, which is what an increasing stack gives us.

def largest_rectangle(heights):
    stack = []                       # indices, heights increasing
    best = 0
    for i, h in enumerate(heights + [0]):    # sentinel 0 flushes the stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

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

When a bar of height h arrives and the top bar is taller, the top bar can no longer extend to the right, because it just met a shorter bar. We pop it and compute its rectangle. The left edge is the new top of the stack (the previous smaller bar), and the right edge is the current index. For the input above, the bars 5 and 6 are popped when the height 2 arrives. Bar 5 gives width 2 and area 10, which is the maximum. The sentinel value 0 added at the end forces every remaining bar to be popped, so no rectangle is missed. Time is O(n) and space is O(n).

A reusable template

1. Create an empty stack that holds indices.
2. Loop over every position i.
3. While the stack is not empty and the new value breaks the order, pop the top and use i to answer for the popped index.
4. Push i.
5. After the loop, anything left on the stack has no answer, so keep the default.

How to recognise a monotonic stack problem

• The statement contains next greater, next smaller, previous greater or how many days until.
• You are asked for the nearest element to the left or right that satisfies a comparison.
• Your first idea is a nested loop that scans forward until a condition is met.
• The problem involves spans, widths or ranges where each element acts as the minimum or maximum, as in histograms.

Common mistakes

• Using the wrong direction. Greater needs a decreasing stack, smaller needs an increasing stack. Test with a tiny example before coding.
• Pushing values instead of indices. You lose the position, which breaks distance and width problems.
• Strict versus non-strict comparison. Popping on < versus <= changes how equal values are treated. Decide what the problem means by greater.
• Forgetting the leftovers. Elements remaining on the stack at the end have no answer, so set their default correctly, or add a sentinel as in the histogram problem.
• Confusing it with a plain stack. Valid Parentheses uses an ordinary stack for matching, with no sorted order. A monotonic stack is specifically about maintaining order.

Complexity summary

If you need a refresher on how to analyse these costs, read our guide to Big O notation for coding interviews, and for the structure we used on linked structures, see linked list interview questions.

Practice problems

• Next Greater Element I and II
• Daily Temperatures
• Online Stock Span
• Largest Rectangle in Histogram
• Trapping Rain Water (also solvable with two pointers, see our two pointers guide)
• Sum of Subarray Minimums (harder)

Common questions

Recap

Greater means a decreasing stack, smaller means an increasing one. Store indices, pop while the order breaks, and answer for each popped item. Trace one tiny example by hand before you code, and check what is left on the stack at the end.

Keep learning: linked list problems, sliding window and heaps and top K build on the ideas in this guide.