Top 13 Monotonic Stack LeetCode Problems, Ranked by Pattern

You have seen the monotonic stack before. You just did not know that is what it was called. You solved the problem, read the editorial, thought "oh, that is clever," and moved on. Then the same problem showed up in a different costume and you stared at it for 40 minutes.

The monotonic stack has exactly five problem shapes. Solve these 13 problems in the right order and you stop recognizing them after the solution. You start seeing them before you write a line of code.

The mental model that unlocks everything: the stack is a waiting room. Elements sit there, waiting to be resolved. Pop is where the answer gets recorded. Push is just filing paperwork. The current element walks in, kicks out everyone it outranks, notes their answers, then sits down itself.

A diagram showing a decreasing monotonic stack resolving two waiting elements when a larger value arrives. Push adds candidates; pop records the answer.

Keep that in mind. It makes the rest obvious.

Next Greater Element: Where Everyone Starts (And Where Most People Stay Too Long)

LC 496: Next Greater Element I (Easy)

You have two arrays. For each element in nums1, find its next greater in nums2. The O(n²) approach writes itself in 30 seconds and will absolutely pass the tests. Do not stop there.

The key insight is that you process nums2, not nums1. Build a decreasing stack while walking nums2. When the current element is bigger than the top, that top element finally has its answer. Pop it, write the answer to a hash map. After one pass through nums2, every element has either an answer in the map or gets -1.

Then look up nums1 results in O(1). Done. Total time O(n). The O(n²) version is doing the same lookups but in the worst possible order.

This one exists to teach the precomputation pattern. You will reuse it in harder problems where the "query array" is buried inside the problem statement and you have to find it yourself.

LC 739: Daily Temperatures (Medium)

How many days until it gets warmer? You could check every future day for every current day. Please do not.

Store indices on the stack, not values. When temperatures[i] beats temperatures[stack.top()], the answer for that index is i - stack.top(). Pop it. Record the gap. Keep walking.

This is the canonical span-counting setup. LC 901, LC 84, and LC 907 all use this exact gap-computation pattern. If you do not have LC 739 down cold, those problems will feel like they came from a different universe.

Circular Arrays (The One Trick That Gets Abused Everywhere)

LC 503: Next Greater Element II (Medium)

Same problem, but the array wraps around. Candidates at the end of the array can have their "next greater" appear near the front. The fix is to run two laps.

Loop from 0 to 2n, index with i % n, and only push indices during the first n iterations. The second lap exists purely to give waiting elements a chance to see the front of the array. They already pushed their paperwork. They just need more candidates to walk through.

def nextGreaterElements(nums: list[int]) -> list[int]:
    n = len(nums)
    result = [-1] * n
    stack = []
    for i in range(2 * n):
        while stack and nums[stack[-1]] < nums[i % n]:
            result[stack.pop()] = nums[i % n]
        if i < n:
            stack.append(i)
    return result

The one trap everyone hits: push only when i < n. Otherwise you enqueue duplicates and your result array gets corrupted. It is not obvious why until you trace through a small example.

Span Accumulation (The Sneaky O(1) Amortized One)

LC 901: Online Stock Span (Medium)

A StockSpanner receives prices one at a time. For each price, return how many consecutive prior days had a price less than or equal to today.

The naive approach re-scans backward each time. It is O(n²) in the worst case and will fail on a monotonically decreasing sequence.

Store (price, span) pairs on the stack, not just prices. When the current price outranks the top, pop it and steal its span. Your current span grows by that amount. After all the popping, push the new combined entry.

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

This is O(1) amortized because each price enters and leaves the stack at most once. LC 901 teaches you that you can carry metadata through the stack. The span field is free cargo.

Histogram and 2D Rectangle (The One Everyone Dreads)

LC 84: Largest Rectangle in Histogram (Hard)

Given bar heights, find the largest rectangle that fits inside. This is the problem that made you question your life choices when you first saw it.

Append a sentinel 0 to the end of the heights array to flush all remaining bars from the stack when you finish.

Stack stores indices. When heights[i] is smaller than the top, that bar can no longer extend rightward. Pop it. Its height is the rectangle height. Its width is i - stack[-1] - 1 after the pop, where stack[-1] is the new top (left boundary). Area follows.

Work through a small example by hand before touching the code. The index arithmetic is what gets people, not the concept. One off-by-one in the width calculation and you are debugging for 20 minutes with no idea why.

LC 85: Maximal Rectangle (Hard)

Binary matrix, find the largest all-1 rectangle. Sounds like a completely different problem.

It is not. It reduces to LC 84. Build a histogram row by row: if the current cell is '1', increment its height; if '0', reset to 0. Run LC 84 on each row's histogram. Take the global maximum.

There is zero new algorithmic content here. The skill being tested is whether you can spot that a 2D problem decomposes into repeated 1D subproblems. Interviewers love this one because it filters out candidates who only pattern-match on surface features.

Water Trapping (Two Solutions, One Reason to Learn Both)

LC 42: Trapping Rain Water (Hard)

The two-pointer approach is simpler, easier to explain in an interview, and probably what you should code if this shows up. But the stack approach is worth understanding because it generalizes.

Trapped water is computed by popping an element and treating it as the floor between two walls. When height[i] > height[stack.top()], pop the floor bar. Water fills the gap: (min(height[i], height[new_top]) - height[floor]) * (i - new_top_idx - 1).

The two-pointer version collapses this into a special case where you only ever track one wall at a time. The stack version handles arbitrary terrain. You will not need the stack version in most interviews. But when you do, you will be very glad you understood it.

Contribution Counting (The Hard Conceptual Jump)

This is where the pattern gets genuinely hard. You stop finding answers for individual elements. You start computing aggregate values over all subarrays by figuring out how much each element contributes.

LC 907: Sum of Subarray Minimums (Medium)

Find the sum of the minimum over every contiguous subarray. Brute force is O(n²) subarrays times O(n) per subarray. That is too slow.

For each element, count the subarrays where it is the minimum. That count is left_dist * right_dist where left_dist is the distance to the nearest strictly smaller element on the left and right_dist is the distance to the nearest smaller-or-equal element on the right. Multiply by the element's value. Sum everything.

Use strict comparison on one side and non-strict on the other. This asymmetry prevents double-counting when duplicates exist. Two equal values cannot both claim to be the minimum of the same subarray. One of them wins based on the tie-breaking direction you chose.

def sumSubarrayMins(nums: list[int]) -> int:
    MOD = 10**9 + 7
    n = len(nums)
    left = [0] * n   # distance to previous smaller (strict)
    right = [0] * n  # distance to next smaller-or-equal (non-strict)
    stack = []
    for i in range(n):
        while stack and nums[stack[-1]] >= nums[i]:  # non-strict for right
            j = stack.pop()
            right[j] = i - j
        stack.append(i)
    for j in stack:
        right[j] = n - j
    stack.clear()
    for i in range(n - 1, -1, -1):
        while stack and nums[stack[-1]] > nums[i]:  # strict for left
            j = stack.pop()
            left[j] = j - i
        stack.append(i)
    for j in stack:
        left[j] = j + 1
    return sum(nums[i] * left[i] * right[i] for i in range(n)) % MOD

The strict/non-strict direction is the single thing candidates get wrong most consistently. Practice it until the choice is obvious, not memorized.

LC 2104: Sum of Subarray Ranges (Medium)

The range of a subarray is its maximum minus its minimum. Sum of ranges = sum of all subarray maximums minus sum of all subarray minimums. Run LC 907's contribution logic twice: a decreasing stack for maximums, an increasing stack for minimums. Subtract.

This problem mostly exists to confirm you understood LC 907 rather than just its solution. If you have to re-derive the logic from scratch, you did not fully get LC 907 yet. Go back.

Greedy Construction (Where the Stack Enforces a Policy)

LC 402: Remove K Digits (Medium)

Remove exactly k digits from a number to make it as small as possible. You have to decide which digits to cut.

Maintain an increasing stack greedily. When the current digit is smaller than the stack top, pop the top (that counts as one removal). After the pass, if k is still positive, chop from the right. Strip leading zeros.

The insight is that a larger digit earlier in the number is always worse than a smaller digit in the same position. Greedily enforcing that takes O(n) with a stack. It is satisfying once it clicks because you can prove optimality with a simple exchange argument: swapping an out-of-order digit never makes the result worse, so doing it eagerly is fine.

LC 316: Remove Duplicate Letters (Hard) / LC 1081

Remove duplicate characters so each appears exactly once and the result is lexicographically smallest. Harder than it looks.

You need three things: a last_occurrence dict, a seen set, and an increasing monotonic stack.

For each character: skip it if already in the result. Otherwise, while the stack top is greater than the current character AND that top character appears later (so removing it now is safe), pop it and mark unseen. Push current.

LC 316 is LC 402 plus a safety check. Before you pop, you have to confirm the character you are removing can actually be reinserted later. Interviewers like this one because it requires layering a greedy constraint on top of the stack invariant. You have to think about two things simultaneously. Most candidates handle one and forget the other.

Non-obvious Signal Problems (The Real Test)

These two look nothing like next greater element. If you see the monotonic stack signal in them, the pattern has become instinct.

LC 456: 132 Pattern (Medium)

Find indices i < j < k where nums[i] < nums[k] < nums[j]. Three nested loops is O(n³). Even O(n²) is too slow.

Scan right to left. Maintain a decreasing stack. Track third, a variable that holds the maximum value ever popped.

When a popped element exceeds third, update third. That value is the "2" (the middle value) in the 132 pattern. When the current element from the right is less than third, you found the "1". Return true.

Scanning right to left with a decreasing stack is the same invariant you already know, just mirrored. You are now looking for previous greater elements instead of next greater elements. The stack machinery is identical. The trick is that you had to flip your perspective 180 degrees to see it.

LC 1944: Number of Visible People in a Queue (Hard)

People stand in a row facing right. Person i sees person j if everyone between them is shorter than both. Process from right to left with a decreasing stack.

For each person i, pop all people shorter than i. The count of visible people is the number popped plus one if the stack is still non-empty (the first taller person blocks everyone behind it and is itself visible).

The pop-count-plus-one formula takes a few examples to internalize. Shorter people popped are visible because nothing blocks them from i's perspective. The first taller person is visible too, but it acts as a wall. Everyone behind it is hidden.

What These 13 Problems Actually Teach You

By the time you finish all of these, a few things become automatic:

Four stack variants: decreasing left-to-right for next greater, increasing left-to-right for next smaller, and their right-to-left mirrors. Every problem is one of these.
Pop is where answers are recorded. Push adds candidates. Never mix these up.
Circular arrays: loop 2n, index with i%n, push only first n iterations.
Contribution counting: pick one side as strict, the other as non-strict. The choice is arbitrary but must be consistent.
Greedy construction problems layer a "is it safe to remove?" check on top of the invariant. LC 402 has no check. LC 316 does.
If a problem asks for sum or aggregate over all subarrays and O(n²) is obvious, contribution counting is probably the intended path.
LC 456 is the litmus test. If you see it and immediately think "monotonic stack, right to left, track the max popped value," the pattern is yours. If you see it and think "nested loops," go back to LC 739.

The gap between grinding these and actually performing in an interview is mostly about narrating the reasoning out loud. Reading a solution is not the same skill as explaining one under pressure. SpaceComplexity runs voice-based mock interviews scored on exactly that dimension, so you find out before it counts whether your verbal walkthrough holds up.

For the recognition layer, how to spot that a problem wants a monotonic stack before you write anything: You Can Recognize Monotonic Stack Problems Before You Code. For the O(n) proof and all four template variants: The Invariant That Turns O(n²) Into O(n). When the problem needs a sliding window maximum instead: The Deque. When the greedy construction sections felt shaky: The Greedy Algorithm covers the exchange argument that makes those solutions provably correct.