vizlearn

Design a stack that reports its minimum in O(1)

Interview QuestionsBy Updated

Keep a second stack of minimums. On push, copy the value onto it whenever it is less than or equal to the current minimum; on pop, remove it from both if it was the top of both. min() is then one read. The <= is the whole question — strictly less breaks on duplicates.

Overview

The question, and what it is testing

Keep a second stack of minimums. On push, copy the value onto it whenever it is less than or equal to the current minimum; on pop, remove it from both if it was the top of both. min() is then one read. The <= is the whole question — strictly less breaks on duplicates.

Stacks & queuesCoding problemMedium

Step through it

What to watch

  • The min stack holds one entry per level at which the minimum changed, not one per element.
  • Pushing 1 twice pushes 1 onto the min stack twice — that is what <= buys.
  • After the pop, the minimum is still 1, because the second copy is underneath.

Say this out loud

"A second stack holding the minimum at each level. Push copies the value onto the min stack when it is less than or equal to the current minimum; pop removes it from the min stack if it matches. min() is the top of that stack, so it is O(1). The trap is using strictly less than, which loses a duplicate minimum on the first pop."

Design a stack that reports its minimum in O(1)

Design a stack with push, pop, top and min, all in O(1).

Run it

Both versions of the comparison, on the sequence that separates them.

1Python
Output
The min stack grows only when the minimum changes, which is the honest answer to how much extra space it costs.
2Python
Output
And the pair variant: easier to get right, at a fixed cost per element.
3Python
Output

                

                

                    
Why a scan is not allowed

                    
The obvious min() walks the stack, which is O(n) and is exactly what the question forbids. Caching a single minimum in a variable is the next attempt and it fails on pop: when the minimum is removed, there is nothing to fall back to, and finding the new one is another scan.
So the structure has to remember the minimum at every level. A parallel stack does that: entry k is the minimum of the first k pushes, so popping a level restores the previous answer for free.

                

                

                    
The <= that everybody gets wrong first

                    
Push 2, then 1, then 1. With < the min stack is [2, 1]; with <= it is [2, 1, 1]. Now pop once. Both versions remove a 1 from the data, and the strictly-less version also removed its only 1 from the min stack — so it reports 2 while a 1 is still in the stack.
The editor below runs both and prints the two answers side by side. It is the single most common bug in this question, and an interviewer who asks for duplicates is asking about exactly this line.

                

                

                    
The one-stack variants

                    
Two alternatives come up as follow-ups, and both are worth knowing.
Store pairs. Push (value, min_so_far) and the minimum is stack[-1][1]. Simpler to get right, and it costs one extra number per element rather than one per new minimum — worse in the best case, identical in the worst.
Store deltas. Keep one stack and push the difference from the current minimum, tracking the minimum in a variable. It is O(1) extra space, it is genuinely clever, and it is fiddly enough that mentioning it as an option scores better than attempting it under time pressure.

                

                

                    
What the question is testing

                    
Whether you can turn "report an aggregate cheaply" into "keep the aggregate as part of the structure". That is the transferable idea: the same move gives a queue with O(1) minimum (two deques, the monotonic one), a sliding-window maximum, and a stack that reports its sum. The interviewer usually follows with one of those.
The second thing being tested is whether you volunteer the duplicate case yourself. Saying "I will use <= so equal minimums each get an entry" before being asked is the answer they are listening for.

                

                

                    
What to say out loud

                    
A second stack holding the minimum at each level. Push copies the value onto the min stack when it is less than or equal to the current minimum; pop removes it from the min stack if it matches. min() is the top of that stack, so it is O(1). The trap is using strictly less than, which loses a duplicate minimum on the first pop.

                

                

                    
Edge cases to raise

                    
Volunteering these is most of what separates a correct answer from a good one.
min() on an empty stack. Decide whether it raises or returns a sentinel, and say which before writing it - an IndexError from self.mins[-1] is a reasonable answer if it is deliberate.
Space is proportional to how often the minimum changes, not to n. An ascending sequence leaves the min stack at length 1; a descending one makes it as long as the data. Worth stating, because it is the honest answer to "how much extra space?"
The two stacks must stay in step. Any method that touches data without considering mins - a clear(), a bulk load, a __setitem__ - is where this class breaks later.

                

                

                    
The follow-ups interviewers ask

                    
"Now make it report the maximum too." One more parallel stack with the comparison mirrored to >=. Worth saying out loud that the duplicate case flips with it - the same <= trap appears as >=, and getting one right and the other wrong is a common slip.
"Can you do it in O(1) extra space?" Yes, by storing the difference from the current minimum rather than the value, and keeping the minimum in a variable. When you pop a value that is the minimum, the stored delta tells you what the previous minimum was. It is genuinely clever and fiddly under time pressure - naming it and then writing the two-stack version is the better answer.
"What about a queue with O(1) minimum?" Harder, and the answer is a monotonic deque rather than a second stack: keep candidates in increasing order and discard from the back anything a new arrival makes irrelevant. That is the same structure as the monotonic stack and as sliding-window maximum.

                

                

                    
Common wrong answers

                    
"Keep the minimum in a variable and update it on push." Correct until the first pop. When the minimum leaves, there is nothing to fall back to and finding the new one is an O(n) scan.
"Sort the stack, or keep it sorted." A sorted stack is not a stack any more - push stops being O(1), and pop returns the wrong element.
"Use min(self.data); it is a builtin so it is fast." Builtin and still O(n). The question asks for O(1), and "it is implemented in C" does not change the complexity.

                

                

                    
Recap in one screen

                    
  • The min stack holds one entry per level at which the minimum changed, not one per element.
  • Pushing 1 twice pushes 1 onto the min stack twice - that is what <= buys.
  • After the pop, the minimum is still 1, because the second copy is underneath.
  • Worth trying: Change <= back to < in MinStack and run the ascending sequence (1, 2, 3). Both versions agree there, which is why the bug survives a casual test.
  • Worth trying: Add a max() as well. One more parallel stack, and the same >= question arrives in mirror image.

                

            


        

    



How the code works
Both versions of the comparison, run on the sequence that separates them, then the pair variant and a size where a scanning min() stops being viable.
How the code works
  1. if not self.mins or x <= self.mins[-1]The <= is the answer to the question. With <, two equal minimums share one entry and the first pop takes it away from both of them.
  2. if self.mins and v == self.mins[-1]Pop from the min stack only when the value leaving is the current minimum. Popping unconditionally would desynchronise the two stacks immediately.
  3. s.mins -> one entry per level where the minimum changedNot one per element. Pushing an ascending sequence leaves the min stack at length 1, which is the best case for space.
  4. current = x if not self.stack else min(x, self.stack[-1][1])The pair variant computes the running minimum once per push and stores it alongside. Easier to write correctly under pressure, at a fixed two slots per element.
Change one thing
  • Change <= back to < in MinStack and run the ascending sequence (1, 2, 3). Both versions agree there, which is why the bug survives a casual test.
  • Add a max() as well. One more parallel stack, and the same >= question arrives in mirror image.
Where this runs
Real CPython, compiled to WebAssembly and running on your own machine — nothing is uploaded. The first run takes a few seconds while the interpreter downloads; after that it is immediate. Need more room, or want to paste your own attempt? Use the Python compiler.


    



Check yourself
0 of 4
Answer without scrolling back up.
  1. Why keep a second stack rather than a single minimum variable?
  2. Why is the comparison on push <= rather than <?
  3. How long is the min stack after pushing 1, 2, 3?
  4. What does the pair variant trade?





 Cheat sheet
Design a stack that reports its minimum in O(1)
Keep a second stack of minimums. On push, copy the value onto it whenever it is less than or equal to the current minimum; on pop, remove it from both if it was the top of both. min() is then one read. The <= is the whole question — strictly less breaks on duplicates.
INTERVIEW · vizlearn.in/interview/design-a-min-stack.html
More in Interview
InterviewEvaluate reverse Polish notationInterviewDaily temperatures, and the monotonic stackInterviewImplement a queue using two stacksInterviewTop k frequent elements
About the author
Ashish Jangra builds and maintains VizLearn. Every module here is written and the visualisation behind it hand-built, so the numbers in a readout come from the same code that draws the picture. Corrections are genuinely welcome and get priority over everything else — if a page states something wrong, or an animation misrepresents what the algorithm does, get in touch.
About VizLearnGitHubLinkedInContact