In this article
Before you start
This page is one step of the coding interviews learning path.
Why interviewers ask this
A monotonic stack turns a problem that looks like it needs a loop inside a loop into a single pass, and interviewers use it to see whether you can find that structure instead of settling for the slow version. It appears under many disguises: the next warmer day, the next greater element, the largest rectangle in a histogram, trapping rain water, and removing k digits to make the smallest number.
A weak answer scans forward from every position and reports quadratic time. A strong answer states the invariant (the stack stays sorted), says what is stored (indexes), says when an answer is produced (when an index is popped), and justifies the linear time. A good candidate also names the choice of strict or non-strict comparison before being asked. The worked example below runs one input end to end.
Monotonic stack from first principles
- Monotonic stack
- A monotonic stack is a stack whose items are kept in increasing or decreasing order by popping every item that violates the order before a new item is pushed, so that popping an item reveals the first later item that beat it.
- Next greater element
- The next greater element of a position in an array is the first value to its right that is larger than the value at that position, or none if no such value exists.
- Amortized cost
- Amortized cost is the average cost per operation over a whole sequence of operations, which can be small even when a single operation is expensive.
In plain words
Picture people standing in line for a photograph. Each person wants to know who is the first taller person behind them. When a taller person arrives, every shorter person in front of them learns the answer and leaves the line. The people still in line are still waiting. The analogy breaks here: in a real line everyone can see everyone, but the algorithm only ever compares the newcomer with the person at the back.
In one precise sentence: scan the array once, keep a stack of positions still waiting for a larger value, and when a larger value arrives, pop every waiting position it beats.
Step 1: A stack adds and removes at the top
A stack supports two moves, push and pop, and both happen at the same end, the top. The last item pushed is the first popped, known as last in, first out (LIFO). In Python a list does the job: the Python tutorial shows append() to push and pop() with no index to remove the top (as of October 2026). Both are fast because they touch only the end of the list.
Input: a value. Output: the value at the top. You now know the one thing a monotonic stack adds: a rule about what is allowed to sit under the new top.
Step 2: Pop every item the new value beats
The rule is applied before every push. Suppose you want the next greater element. When a new value arrives, look at the top of the stack. While the top is smaller than the new value, the new value is the first larger value to the right of that top, so the top has found its answer and is removed. Stop when the top is not smaller, or the stack is empty. After the popping, the stack read from bottom to top never increases (equal values may sit together), which is where the word monotonic comes from.
Nothing is lost by popping. An item that was popped has its answer; an item that stays has not met a larger value yet and may still need one. The stack therefore holds exactly the items still waiting.
Step 3: Store indexes, and answer when an item is popped
The stack should hold indexes, not values. A value lets you compare, but an answer such as "how many days until a warmer day" needs a distance, and the distance is the difference of two positions. So store the position i of each item, compare through temps[i], and when position j is popped by position i write i - j into the answer for j.
Take the temperatures 73, 74, 75, 71, 69, 72, 76, 73. Position 0 (73) is pushed. Position 1 (74) pops 0 and writes 1. Position 2 (75) pops 1 and writes 1. Positions 3 and 4 (71, 69) are pushed. Position 5 (72) pops 4 and then 3, writing 1 and 2. Position 6 (76) pops 5 and 2, writing 1 and 4. Position 7 (73) pops nothing. The positions left on the stack, 6 and 7, get 0 because no warmer day follows.1 The final answer is 1, 1, 4, 2, 1, 1, 0, 0.
Step 4: Each item is pushed once and popped at most once
The code has a loop inside a loop, yet the total work is linear. Every position is pushed exactly once, and a position can be popped at most once, so the inner loop does at most n pops across the whole run, not n per position. The standard write-up of the algorithm states this as "every iteration of the inner loop removes an item that had been added in some previous iteration of the outer loop" (Wikipedia, all nearest smaller values, read October 2026).
That is amortized cost: each pop is paid for by the single push that put that item on the stack, so the n pushes cover every pop. The problem of finding the nearest smaller value for every element was studied formally by Berkman, Schieber and Vishkin (1993).
Step-by-step description
- Push and pop happen at the top.
- A new item pops every smaller top.
- Answer is the new index minus the popped one.
- Each index goes in once, out at most once.
- Every position is pushed exactly once.
- A position can be popped at most once.
- A position learns its answer when a later position pops it.
Knowing it is half the job. Saying it is the other half.
Interview Clozo is an AI interview copilot for real interview rounds: it hears the question and puts a strong answer on your screen, and you say it in your own words. See the features or how it works.
Start Free Trial →Worked example
The eight temperatures above need eight pushes and six pops, and the stack never holds more than three positions.1 Here is the whole trace. Read the table row by row: the second column is the temperature, the third lists positions popped, and the last shows the stack of positions after the push.
| Position | Temperature | Popped positions | Stack after push |
|---|---|---|---|
| 0 | 73 | none | 0 |
| 1 | 74 | 0 | 1 |
| 2 | 75 | 1 | 2 |
| 3 | 71 | none | 2, 3 |
| 4 | 69 | none | 2, 3, 4 |
| 5 | 72 | 4, 3 | 2, 5 |
| 6 | 76 | 5, 2 | 6 |
| 7 | 73 | none | 6, 7 |
Text description of the diagram
- The stack never holds more than three positions.
- The eight temperatures need eight pushes and six pops.
Counting comparisons shows why it matters. On a run of 1,000 strictly decreasing values, nothing is ever popped and a stack pass makes 999 comparisons, while a brute-force scan from every position makes 499,500.1 On 1,000 strictly increasing values, every position pops the one before it and both methods make 999 comparisons, since the answer is always the next position. On a pseudo-random zigzag of 1,000 values (illustrative), the stack needs 1,973 comparisons against 8,266 for brute force.1 The stack never needs more than about two comparisons per item, because each item is pushed once and popped at most once.
Text description of the diagram
- On 1,000 decreasing values a stack pass makes 999 comparisons while brute force makes 499,500.
- On the zigzag of 1,000 values the stack needs 1,973 comparisons against 8,266 for brute force.
The same idea solves the largest rectangle in a histogram. Take bar heights 2, 1, 5, 6, 2, 3. Keep a stack of bar indexes whose heights increase. When a shorter bar arrives at position i, pop each taller bar: its rectangle has the popped bar's height, and its width is the number of bars strictly between the bar now on top and i, which is i minus the top's index minus 1 (or i if the stack is empty).
After the last bar, pop what is left with i equal to n. In this example the best area is 10: when the bar of height 2 arrives at position 4, popping the 5 at position 2 leaves position 1 on top, so the width is 4 − 1 − 1 = 2 and the area is 5 × 2 = 10.1
Trade-offs and edge cases
A monotonic stack costs O(n) time and O(n) extra space, since in the worst case every position waits on the stack at once, as in the strictly decreasing run above. Four edge cases decide most interview bugs.
Equal values. Whether to pop an item equal to the new value depends on the question. When answers are written at pop time (next greater), "strictly greater" pops only smaller tops and "greater or equal" pops smaller or equal tops; the previous-greater direction below reverses this. Decide this from the wording, and test a case with duplicates.
Direction. For the next smaller element, flip the comparison so the stack is increasing. For the previous greater or smaller element, read the top of the stack before pushing: whatever remains there after the popping is the answer for the new position. The equality rule flips here: for the previous strictly greater element, pop tops that are smaller or equal, so an equal value never stays on top as the answer; for 5, 5 the second 5 then has no previous greater element.
Circular arrays. For a circular array, pass over the array twice, or over indexes 0 to 2n minus 1 using the index modulo n, push only during the first n steps, but keep popping and recording answers in both passes, because an item near the end can find its larger value at the start. Items still on the stack at the end have no greater element anywhere in the circle; for 1, 2, 1 the answers are 2, none, 2.
Sliding windows. When the answer must come from a moving window, items also expire from the front, which a stack cannot do. Use a double-ended queue with the same pop-from-the-back rule, called a monotonic queue; Python's collections.deque supports it because it has "fast appends and pops from both ends" (Python tutorial, as of October 2026). A plain list is slow at the front.
For other patterns that turn quadratic work into a single pass, see the coding interviews hub, the machine learning coding hub, topological sort and k closest points to origin. For how a coding round fits into the whole process, see the interview loops hub.
How to answer it in an interview
How would you find, for each day, how many days until a warmer one?
I would use a monotonic stack of day indexes. I scan once; for each day I pop every index whose temperature is lower than today's, and for each popped index j I write today's index minus j as its answer. Then I push today's index. The stack stays decreasing in temperature, so it holds only days still waiting for a warmer one. Each index is pushed once and popped at most once, so the time is O(n) and the space is O(n). Days left on the stack get zero. I would store indexes because the answer is a distance.
The answer structure: name the structure, say the invariant, say what you store and when you answer, then give the cost.
Common mistakes
- "I push the temperatures onto the stack." (wrong) A value cannot give the distance to a later value. (right) "I push indexes and look the value up through the array."
- "It is O(n squared) because of the nested loop." (wrong) The inner loop pops each item at most once overall. (right) "It is O(n) because every item is pushed once and popped at most once."
- "I use less than for every problem." (wrong) The choice of strict or non-strict decides how duplicates behave. (right) "I pick the comparison from the wording and test duplicates."
- "I answer when I push." (wrong) A position does not know its answer yet when it is pushed. (right) "A position learns its answer when a later position pops it."
Follow-up questions
How do you implement a Max Stack with push, pop, top, peekMax and popMax?
Keep the items in a doubly linked list and an ordered map (or a heap with lazy deletion) from value to nodes. peekMax reads the largest key, and popMax unlinks that node from both. top is O(1) and the other operations O(log n). A running maximum beside each entry gives push, pop, top and peekMax in O(1) but cannot pop the maximum quickly. A Max Stack is a design problem; a monotonic stack is a technique that deliberately discards items.
Can popMax run in O(1)?
Only if push pays for it. If push and popMax were both O(1), n pushes followed by n popMax calls would sort n values in O(n) comparisons, below the n log n lower bound for comparison sorting. A sorted linked list beside the stack makes popMax O(1) but push O(n); the ordered-map design keeps both at O(log n).
How do you find the next greater element in a circular array?
Loop over 2n positions using the index modulo n, push only during the first n, and keep popping and answering in both passes. Items still on the stack at the end have no greater element anywhere in the circle.
Is removing the fewest characters to balance parentheses a monotonic stack problem?
No. It uses a plain stack of the indexes of unmatched opening brackets, not a monotonic stack: push the index of each (, pop on a matching ), and delete every unmatched ) and every index left on the stack.
Why is a monotonic stack O(n) when it has a loop inside a loop?
Each position is pushed once and popped at most once, so the pops across the whole run total at most n. The amortized cost per position is constant.
- A monotonic stack keeps its items sorted by popping any that the new item beats.
- Store indexes, and write an answer when an index is popped.
- Each index is pushed once and popped at most once, so the pass is O(n).
- Decide strict or non-strict comparison from the wording, and test duplicates.
- Use a monotonic queue when items also expire from the front.
Sources
- Optimal doubly logarithmic parallel algorithms based on finding all nearest smaller values — Journal of Algorithms 14(3) (Berkman, Schieber, Vishkin), 1 May 1993
- All nearest smaller values — Wikipedia (date = read date), 24 Oct 2026
- Data Structures: using lists as stacks (The Python Tutorial) — Python Software Foundation (date = read date), 24 Oct 2026
