Home / Blog / Monotonic Stack Interview Pattern

Monotonic Stack Interview Pattern

Published 2026-10-09 · Luna Interview

The monotonic stack interview pattern shows up whenever you need the next greater, next smaller, or a sliding window of candidates that stays ordered. Interviewers like it because the idea is short to state and easy to mess up on indices, ties, and empty-stack edges. This guide gives you a recognition checklist, increasing vs decreasing choice, and talk tracks you can reuse without sounding scripted.

What “monotonic” means here

A monotonic stack keeps elements in sorted order—strictly or non-strictly—by popping anything that would break the order when a new element arrives. You are not sorting the whole array; you are maintaining a frontier of candidates that still matter for future answers.

Typical jobs:

• Next greater element (NGE) / previous greater
• Next smaller / previous smaller
• Largest rectangle in histogram
• Daily temperatures / span of stock price
• Remove duplicate letters with lexicographically smallest result (stack + greediness)
• Sliding window maximum (deque variant of the same idea)

If the prompt asks “for each index, find the nearest … to the left/right,” hear monotonic stack before you reach for nested loops.

Recognition checklist

Say yes to stack when:

1. You need nearest left or right neighbor with a comparison (>, >=, <, <=)
2. Brute force is O(n²) “look ahead until condition”
3. Order of processing is left-to-right or right-to-left once
4. Answers depend on a frontier of still-unresolved indices

Say no (or not first) when:

• You need global order of all elements → sort or heap
• You need shortest path on a graph → BFS/Dijkstra
• The window is fixed size and you only care about sum → sliding window / prefix

Talk track:

“Each index needs the next greater to the right; nested loops are O(n²). I’ll keep a decreasing stack of unresolved indices and resolve them when a greater value arrives—O(n) amortized.”

Increasing vs decreasing (pick deliberately)

People mix the labels. Prefer describing what you pop on rather than arguing about the adjective:

Talk track:

“I’ll store indices in a stack where values are strictly decreasing from bottom to top. When nums[i] is greater than the top, I pop and set that popped index’s next-greater to i.”

Index stack, not value stack

Store indices (or index + value pairs). You almost always need the position to write the answer array and to compute widths. Values alone lose distance.

Template skeleton (next greater to the right):

1. answer[i] = -1 (or sentinel) for all i
2. Empty stack of indices
3. For i from 0 to n-1:

- While stack not empty and nums[i] > nums[stack.top]: pop j, set answer[j] = nums[i] (or i) - Push i

1. Leftovers never got a greater → keep sentinel

Previous greater: walk right-to-left, or keep a different invariant. State the direction out loud before coding.

Strict vs non-strict comparisons

Interviewers love ties.

• Next strictly greater: pop while nums[i] > nums[top]
• Next greater or equal: pop while nums[i] >= nums[top] (rarer; confirm the prompt)

For “remove duplicates keep order / smallest string,” equality handling and “still available later” counts change the pops. Restate the requirement before you choose > vs >=.

Complexity you should say

• Time: O(n) — each index pushed and popped at most once
• Extra space: O(n) for the stack in the worst case (strictly decreasing input for a “next greater” stack)

Do not claim O(1) space unless the problem allows mutating the input as the answer and the stack is bounded—usually it is not.

Worked mental picture: daily temperatures

Given temperatures, for each day how many days until a warmer day?

• Stack holds indices of days still waiting for warmer weather
• Values on the stack are decreasing (colder waiting days)
• When a warmer day arrives, pop and set answer[j] = i - j

Talk track:

“Unresolved colder days sit on a decreasing stack. A warmer day settles the top until the stack is empty or still colder. Distance is index difference.”

Histogram rectangle (same pattern, wider story)

Largest rectangle in histogram is monotonic stack with widths:

• For each bar, find previous smaller and next smaller
• Width = next - prev - 1, area = height * width
• Stack of increasing heights; pop when a smaller bar arrives

Narrate why smaller neighbors bound the rectangle before you dive into code. The stack is the tool; the geometry is the insight.

Common bugs (name them before they bite)

1. Off-by-one on width — draw one example with indices
2. Forgetting leftovers — indices still on the stack at the end
3. Pushing values only — then needing indices later
4. Wrong comparison on ties — confirm strictness
5. Circular arrays (next greater II) — process 2n with i % n, but push logic carefully so you do not double-assign
6. Empty stack access — always check before peek/pop

Communication script (first two minutes)

1. Restate: nearest greater/smaller left/right, or histogram/span variant
2. Brute force: nested scan — O(n²)
3. Insight: each element resolves earlier waiters → stack
4. Invariant: “stack values are … ; we pop when …”
5. Complexity: O(n) time, O(n) space
6. Dry-run three indices including a tie and an end-of-array case

Practice set (pattern coverage)

Do not grind fifty variants. Do five until the invariant sentence is automatic.

Soft practice note

Monotonic stack interviews reward a clear invariant more than clever tricks. If you want a Chrome side panel to rehearse the “decreasing stack of indices / pop on greater” talk track under timed pressure, Luna Interview is built for calm coding rehearsal. Use it to build fluency—not to skip the dry-run or to violate interview rules.

Day-of checklist

• [ ] Prompt mapped to next/prev greater or smaller (or histogram)
• [ ] Increasing vs decreasing justified in one sentence
• [ ] Stack stores indices
• [ ] Strict vs non-strict comparison confirmed
• [ ] O(n) amortized complexity spoken
• [ ] Tie + empty + end-of-array dry-run done
• [ ] Leftover stack indices handled

Keep the stack ordered and the invariant loud—that is the monotonic stack interview pattern.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.