You Can Recognize Monotonic Stack Problems Before You Code

The problem says "Daily Temperatures." You stare at an array of integers and think: maybe a hash map? Or two pointers? Surely there's a sorting trick. You write a brute-force nested loop. It passes all the small test cases, because of course it does. Then comes the time limit exceeded banner and the interviewer leaning forward: "Can you do better?"

You can. You just don't know it yet. And the thing keeping you stuck isn't the implementation. It's recognition.

Monotonic stack problems share five recognizable shapes. Spotting them is a separate skill from knowing how to code the data structure. Once you see those shapes, the solution is almost mechanical. If you want the full reference with 14 language implementations, the monotonic stack reference has that. This post is about not getting caught staring at the TLE banner.

Five Signals That Scream "Monotonic Stack"

Monotonic stack problems don't say "use a monotonic stack." They use coded language. Train yourself to spot these five shapes:

1. "Next/previous greater/smaller element." The most direct signal. If the problem asks you to find, for each element, the nearest element that is larger or smaller in some direction, stop and write the monotonic stack template. Don't overthink it. This is the canonical case, and it shows up in disguise constantly.

2. "How many days until..." or "how many consecutive..." phrasing. Daily Temperatures, Stock Span Problem, and Gas Station variants often wear this costume. The framing is always "count until some condition holds relative to this element." Write those words in your notes and draw a line to the stack template.

3. "Largest rectangle" or "maximum area" in a bar chart. The Largest Rectangle in Histogram (LC 84) and Maximal Rectangle (LC 85) are the canonical examples. Any time you're computing areas where the height of a rectangle is determined by a minimum, the monotonic stack is triangulating those minima for you. When you see bars and areas, reach for it immediately.

4. O(n) required, and your brute force scans left or right per element. If your nested loop looks like "for each element, look left until you find something smaller," that's exactly the pattern the stack was designed to collapse. This is different from the sliding window pattern, which shrinks and grows a contiguous range. Monotonic stack is per-element boundary search, not a window.

5. Contribution counting over subarrays. "Sum of subarray minimums" (LC 907), "sum of subarray ranges" (LC 2104). These problems ask you to aggregate across all subarrays. The key move is flipping the question: instead of "what is the minimum of each subarray?", ask "for each element, how many subarrays is it the minimum of?" A monotonic stack finds those boundaries in O(n). This one trips people up because it doesn't look like a stack problem at all until you flip it.

If two or more of these signals appear in one problem, you're almost certainly looking at a monotonic stack. Signal 1 or 3 alone is usually enough to commit.

The Stack Is a Waiting Room

The standard explanation focuses on the sorted property: "elements are in increasing (or decreasing) order." That's true, but it doesn't explain why it helps.

Think of the stack as a waiting room. Elements enter and wait. They're waiting for the first element that resolves their query, the first thing to their right that is larger (or smaller) than them. Think of it like waiting for a bus that only comes if you're smaller than the next passenger. When the resolving element arrives, the waiting elements get their answer and leave.

In "Next Greater Element," element at index j waits on the stack. When element at index i arrives and arr[i] > arr[j], element j gets its answer: i (or arr[i]). It leaves the stack. The current iteration isn't primarily about processing i. It's about resolving everyone i is larger than.

The pop event is where the answer gets recorded, not the push.

The iteration is not "push me, skip the rest." It's "before I push myself, I resolve anyone I can answer, then I wait for whoever answers me." Every element eventually either resolves someone or gets left on the stack unanswered.

Diagram showing element 5 arriving and resolving two waiting stack elements simultaneously, filling result[0] and result[1] in a single pass

One Template, Four Directions

The base template for next greater element, with a decreasing stack:

def next_greater(arr):
    n = len(arr)
    result = [-1] * n
    stack = []  # stores indices

    for i in range(n):
        while stack and arr[i] > arr[stack[-1]]:
            j = stack.pop()
            result[j] = arr[i]   # i is j's next greater element
        stack.append(i)

    return result

Three implementation rules you should memorize:

Store indices, not values. You need the index to write into result[j], and you can always recover the value with arr[stack[-1]].
The pop condition determines what you find. arr[i] > arr[stack[-1]] finds next greater. Flip to < for next smaller.
After the loop, anything still on the stack found no answer. Leave those at -1 (or 0 for width problems like histograms).

The four directional variants come from two binary choices: left-or-right scan, greater-or-smaller comparison.

Variant	Scan direction	Pop condition	Stack type
Next greater	Left to right	`arr[i] > top`	Decreasing
Next smaller	Left to right	`arr[i] < top`	Increasing
Previous greater	Right to left	`arr[i] > top`	Decreasing
Previous smaller	Right to left	`arr[i] < top`	Increasing

Pick the direction (which side do you want the answer on?) and the comparison (greater or smaller?), then run the template. The mechanical part is genuinely mechanical once you've identified the pattern.

One adjacent thing worth knowing: when the problem asks for the maximum in a sliding window rather than the next greater element for a fixed position, reach for a monotonic deque instead. Same invariant, different data structure because you need O(1) access to both ends. The monotonic deque guide covers that. Fixed window size is the signal to use it.

Why There's No O(n²) In Here

The template has a while inside a for. That looks O(n²). It isn't, and this is one of those amortization arguments that you should be able to explain out loud without hesitating.

Each element is pushed onto the stack exactly once and popped at most once. The while loop can only pop elements that were pushed. Total pushes: n. Total pops: at most n. Total work: 2n = O(n).

The nested loop is not doing O(n) work per outer iteration. It's amortizing across the entire pass. The more elements popped in one iteration, the fewer remain for future iterations. The budget is fixed at n pops for the whole array. A while inside a for is not automatically O(n²). It depends on how much total work the inner loop can possibly do.

Code comment reading "I don't know what I did but it works // Please don't modify it" above a Java function that computes square(n) by incrementing k in a while(true) loop until k == n*n

Not all nested loops are O(n²). But this one definitely is.

Three Traps That Will Bite You Once

Trap 1: strict vs. non-strict, and why duplicates destroy contribution counting.

The pop condition arr[i] > arr[stack[-1]] is strict: equal elements stay on the stack. Use >= to also pop equals. For basic next-greater problems, strict is usually correct. For contribution counting with duplicates, you need asymmetric treatment: use strict < on one boundary and non-strict <= on the other.

In LC 907 (Sum of Subarray Minimums), with array [3, 1, 2, 1], both 1s could claim overlapping subarrays as their minimum. Use asymmetric comparison so each subarray gets claimed by exactly one element. Same comparison on both sides and you either double-count or miss ranges. Test this specific array before you submit anything involving contribution counting.

Trap 2: circular arrays need a double pass.

LC 503 (Next Greater Element II) is circular. The first element might find its answer somewhere after wrapping around. Iterate 2n times, use i % n for array access, and push indices only during the first n iterations to avoid duplicates.

for i in range(2 * n):
    while stack and arr[i % n] > arr[stack[-1]]:
        result[stack.pop()] = arr[i % n]
    if i < n:
        stack.append(i % n)

The if i < n guard is easy to forget and produces wrong answers silently.

Trap 3: forgetting to drain the stack.

After the main loop, elements still on the stack have no answer. For most problems that's fine; they keep their default -1. Histogram problems are different: remaining elements still contribute rectangles, and missing them means missing the globally largest one.

The cleanest fix: append a sentinel 0 to the array before processing. A bar of height 0 is smaller than everything, flushing the entire stack automatically. No post-loop cleanup needed.

heights.append(0)  # sentinel: forces all remaining bars off the stack

One line. Prevents a whole category of wrong answers on histogram problems.

When the Problem Says "Sum Across All Subarrays"

When a problem says "sum across all subarrays" and involves a min or max, flip the question. Instead of iterating over subarrays in O(n²), ask: for each element, how many subarrays is it the minimum of?

For element at index i with value v:

left = distance to the previous element smaller than v (or the left edge of the array).
right = distance to the next element smaller than or equal to v (or the right edge).
Element i is the minimum of left * right subarrays and contributes v * left * right to the total.

A single left-to-right monotonic stack pass gives you both left and right for every element simultaneously, since each pop resolves both boundaries for the popped element. That's what makes LC 907 O(n) instead of O(n²).

Before You Start Coding

Spend thirty seconds on this checklist before writing a single line of code:

Nearest greater or smaller in some direction? Monotonic stack.
Brute force is "scan until condition met" per element? Monotonic stack.
Summing across all subarrays involving a min or max? Contribution technique.
Circular array? Double the loop, modulo index, push only the first half.
Duplicates in a contribution problem? Asymmetric strict/non-strict comparison.

Once you've identified the shape, the template writes itself. Three lines: while stack and condition: pop and record; push current. Everything else is bookkeeping.

Image showing a lock puzzle where someone uses a brute-force Java loop to try all combinations, captioned "Brute force wins."

Two weeks of LeetCode medium prep, and you still reach for the nested loop when the clock starts.

If you want to practice explaining this under pressure, SpaceComplexity runs voice-based mock interviews with rubric-based feedback on exactly this kind of pattern-recognition question. Knowing the answer in your head and explaining it out loud to an interviewer are very different skills.