Monotonic Stack LeetCode Pattern Guide — Next Greater Element and Histogram Problems

This monotonic stack LeetCode pattern guide covers the family of problems where each item needs to find the nearest previous or next item that is greater, smaller, or otherwise blocks it. The headline examples are next greater element and histogram problems, but the same idea appears in daily temperatures, stock span, removing digits, visibility, and contribution-counting questions. Once you learn the invariant, the pattern becomes less mysterious: keep a stack whose values are ordered, and pop when the current element resolves the question for earlier elements.

The interview skill is not “use a stack.” It is knowing what the stack represents, why popped elements will never be needed again, and whether equal values should stay or go.

The core idea

A monotonic stack stores candidates in increasing or decreasing order. It is useful when a future item can eliminate past candidates.

• Monotonic decreasing stack: values from bottom to top are decreasing. Useful for finding the next greater element, because a new larger value pops smaller unresolved values.
• Monotonic increasing stack: values from bottom to top are increasing. Useful for finding the next smaller element, histogram boundaries, or removing larger digits.

Usually the stack stores indexes, not just values. Indexes let you compute distances, widths, and assign results.

A good invariant sounds like this:

“After processing index i, the stack contains indexes whose answer has not been found yet, ordered so that each remaining item is a better blocker candidate than the one above it.”

That sentence explains both correctness and runtime. Each index is pushed once and popped once, so the algorithm is O(n), even if the inner while loop looks nested.

Next greater element template

For “next greater element to the right,” scan left to right with a decreasing stack.

def next_greater(nums):
    ans = [-1] * len(nums)
    stack = []  # indexes, values decreasing

    for i, x in enumerate(nums):
        while stack and nums[stack[-1]] < x:
            j = stack.pop()
            ans[j] = x
        stack.append(i)

    return ans

When x arrives, it is the first greater element for every smaller value on top of the stack. Why first? Because those indexes have survived every element between them and i; if a greater element had appeared earlier, they would have been popped already.

For “daily temperatures,” the result is a distance, not 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
        stack.append(i)
    return ans

The only change is assigning i - j. This is why storing indexes is the default.

Previous greater, next smaller, and direction choices

Most monotonic stack problems are one of four queries:

| Query | Scan direction | Stack order | Pop while | |---|---|---|---| | Next greater to right | Left to right | Decreasing | stack_top < current | | Next smaller to right | Left to right | Increasing | stack_top > current | | Previous greater to left | Left to right | Decreasing after popping smaller/equal blockers | stack_top <= current if strict | | Previous smaller to left | Left to right | Increasing after popping larger/equal blockers | stack_top >= current if strict |

The direction is about when the answer becomes available. If current elements answer questions for previous elements, scan left to right. If future elements should see the nearest blocker on their left, you can often still scan left to right but read the stack top after popping invalid candidates.

For circular arrays, scan twice and use modulo indexes. Push only during the first pass or guard assignments carefully.

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

The equal-values decision

Equal values are the most common source of wrong answers. Decide whether the problem asks for strictly greater/smaller or greater-or-equal/smaller-or-equal.

• If the answer must be strictly greater, do not pop equal values when resolving next greater; use < current.
• If equal values should not block each other for a boundary, pop with <= or >= depending on direction.
• In contribution-counting problems, use asymmetric equality rules so duplicate values are counted once, not twice.

For example, in “sum of subarray minimums,” you often compute previous less strictly and next less-or-equal, or vice versa. That asymmetry assigns each subarray with duplicate minimums to exactly one index.

A quick interview phrase: “I’m choosing strict on the left and non-strict on the right to break ties consistently for duplicates.”

Largest rectangle in histogram

Histogram is the signature monotonic stack problem because it uses boundaries instead of direct answers. For each bar, you need the widest interval where that bar is the minimum height. The nearest smaller bar on the left and right define that width.

The one-pass sentinel template:

def largest_rectangle_area(heights):
    stack = []  # indexes with increasing heights
    best = 0

    for i, h in enumerate(heights + [0]):
        while stack and heights[stack[-1]] > h:
            j = stack.pop()
            height = heights[j]
            left_boundary = stack[-1] if stack else -1
            width = i - left_boundary - 1
            best = max(best, height * width)
        stack.append(i)

    return best

The sentinel 0 flushes all remaining bars. When bar j is popped, current index i is the first smaller bar to the right. The new stack top is the first smaller bar to the left. Everything between those boundaries has height at least heights[j], so heights[j] * width is the largest rectangle where j is the limiting height.

This explanation is interview gold because it turns a memorized trick into a boundary proof.

Removing digits and building the best sequence

Monotonic stacks also solve “remove k digits” and lexicographic sequence problems. The pattern is replacement: when a better current digit arrives, pop worse previous digits while you still have removals left.

def remove_k_digits(num, k):
    stack = []
    for ch in num:
        while k and stack and stack[-1] > ch:
            stack.pop()
            k -= 1
        stack.append(ch)

    if k:
        stack = stack[:-k]
    return ''.join(stack).lstrip('0') or '0'

The invariant is that the stack is the smallest prefix possible after processing the current character and spending the removals already used. If a larger digit sits before a smaller digit, exchanging them by deletion improves the number immediately.

How to recognize the pattern

Look for these signals:

• The problem asks for nearest greater, nearest smaller, warmer day, lower price, visible person, or span.
• A naive solution scans left or right from every index.
• Once a candidate is beaten by a later value, it can never be the answer for future positions.
• You need widths between blockers, not all pairs.
• The desired runtime is O(n), but there is no obvious two-pointer window.

If the problem needs arbitrary removals from the middle of a previously built answer, monotonic stack may still apply. If removed items can become useful again later, it probably does not.

Common traps

• Storing values instead of indexes. Values lose distance and duplicate identity.
• Using if instead of while. One current value may resolve many stacked values.
• Popping on the wrong equality. Write down strictness before coding.
• Forgetting the sentinel in histogram. Remaining increasing bars never get processed.
• Misreading stack order. A decreasing stack means values decrease from bottom to top; it pops when a bigger value arrives.
• Claiming O(n²). The loop is amortized O(n) because each item pops once.

Practice checklist

Before submitting, answer these questions:

1. What does each stack entry represent?
2. Is the stack increasing or decreasing by value?
3. What event causes an item to pop?
4. When an item pops, what answer or boundary is now known?
5. Should equal values be popped?
6. Do I need a sentinel or second pass?
7. Am I returning value, index, distance, width, or count?

This checklist catches most bugs before the test suite does.

How to talk about monotonic stacks in interviews and resumes

In interviews, lead with the invariant:

“I’ll keep a decreasing stack of unresolved indexes. When a warmer temperature arrives, it resolves every smaller temperature on top of the stack because none of the intervening days was warm enough. Each index is pushed and popped at most once, so the runtime is linear.”

On a resume or project write-up, connect the pattern to user-visible impact:

• “Reduced repeated range scans from O(n²) to O(n) by replacing nested comparisons with a monotonic stack.”
• “Computed nearest-threshold events for time-series data using stack-maintained blocker boundaries.”
• “Implemented histogram-style boundary calculation to identify maximal contiguous capacity regions.”

Monotonic stack problems feel tricky because the code is short and the invariant is dense. Practice naming the unresolved candidates, the pop condition, and the boundary discovered at pop time. Once those three pieces are clear, next greater element and histogram problems become variations instead of separate tricks.

A small dry run technique

When a monotonic stack solution is not clicking, dry run with three columns: current index, stack contents, and what gets resolved. For temps = [73, 74, 75, 71, 69, 72, 76], indexes 0 and 1 pop as soon as warmer days arrive, while 3 and 4 wait until 72. The stack after processing 69 contains unresolved days with decreasing temperatures: 75, 71, 69. When 72 arrives, it resolves 69 and 71, but not 75.

This table-based dry run prevents two mistakes. First, it reminds you that the stack contains unresolved candidates, not the final answer. Second, it proves why popping is safe: once 72 answers 69, that 69 can never be useful for a later day because 72 is closer and warmer. In interviews, a 30-second dry run can rescue a solution that otherwise sounds like memorized syntax.

One-line pattern summary

If you need a compact way to remember the pattern, use this sentence: “The stack keeps unresolved indexes in an order that makes the top easiest to invalidate.” For next greater element, the easiest item to invalidate is the smallest recent value, so a larger current value pops it. For next smaller boundaries, the easiest item to invalidate is the largest recent value, so a smaller current value pops it. This wording helps you rebuild the template even if you forget the exact comparison operator.

Related guides

• DFS LeetCode Pattern Guide — Recursion Templates and Grid/Graph Problems — A DFS LeetCode pattern guide with recursion templates, visited-set rules, grid and graph examples, backtracking structure, complexity notes, and interview pitfalls.
• Topological Sort LeetCode Pattern Guide — Course Schedule and Dependency Problems — A practical topological sort LeetCode pattern guide for Course Schedule, dependency ordering, cycle detection, Kahn’s algorithm, DFS ordering, and common graph-building mistakes.
• Trie LeetCode Pattern Guide — Prefix Search, Autocomplete, and Word Problems — A practical trie pattern guide for LeetCode interviews: when prefix trees beat hash sets, how to code the templates, and how to handle autocomplete, wildcard search, and board word problems.
• Backtracking LeetCode Pattern Guide — Permutations, Combinations, and Subsets — A practical backtracking LeetCode pattern guide with templates, decision rules, duplicate-handling tricks, pruning advice, and interview talk tracks for permutations, combinations, subsets, and constraint problems.
• BFS LeetCode Pattern Guide — Shortest-Path, Level-Order, and Multi-Source — A BFS LeetCode pattern guide for recognizing queue-based problems, implementing level-order traversal, solving unweighted shortest paths, using multi-source BFS, and avoiding common visited-state bugs.