The problem
Design a stack that supports push, pop, top, and getMin (the smallest value currently in the stack), all in constant time.
Input: push 5, push 3, push 7, min, pop, push 2, min, pop, pop, min Output: min → 3, pop → 7, min → 2, pop → 2, pop → 3, min → 5
Picture it
Picture a stack of plates where each plate carries a sticky note saying “the lightest plate in the pile when I was added”. To answer “what’s the lightest?” you just read the note on the top plate. When you take the top plate off, the plate underneath still has the correct note for the smaller pile.
How to recognise it
- You are asked to design a class, and every operation must be O(1), including a query (the minimum) that a plain stack cannot answer quickly.
- Items only come and go at one end, so the set of items below any position never changes while that position is in the stack.
- That means a summary of "everything at or below here" (the minimum, maximum or sum) can be computed once on push and stored, and it stays correct until that item is popped.
- Up to 3 × 10^4 calls, so a scan of the whole stack on every
get_minis too slow to rely on.
Start with brute force
Use a normal list for the stack and compute the minimum on demand with min.
class MinStackBrute:
def __init__(self):
self.stack = []
def push(self, x):
self.stack.append(x)
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return min(self.stack)
Push, pop and top are O(1), but get_min is O(n) because it scans the whole stack. With 1.5 × 10^4 pushes followed by 1.5 × 10^4 get_min calls, that is about 2.25 × 10^8 comparisons, and the task explicitly asks for constant time.
From brute force to the idea
- Find the waste. Every
get_minrescans items that have not changed since the last call. The items below the top only change when they are popped themselves. - Ask what the minimum depends on. The minimum of the whole stack is the minimum of the items from the bottom up to the top. When a new item lands on top, the new minimum is
min(x, old minimum). - Store it with the item. The shown code pushes a pair
(value, min so far). Thelowit stores isxfor the first item, and otherwise the smaller ofxand the stored minimum of the item below. - Popping needs no repair. Removing the top pair exposes the pair below it, whose stored minimum was correct for exactly the items that remain.
- Answer from the top.
topreadsself.stack[-1][0]andget_minreadsself.stack[-1][1], both O(1).
This is the key idea: each entry remembers the minimum of itself and everything beneath it, so popping automatically restores the old minimum.
The key idea
Store (value, minimum so far) with every entry. The top entry always knows the current minimum: every operation is O(1).
Python solution
class MinStack:
def __init__(self):
self.stack = [] # (value, min so far)
def push(self, x):
low = min(x, self.stack[-1][1]) if self.stack else x
self.stack.append((x, low))
def pop(self):
self.stack.pop()
def top(self):
return self.stack[-1][0]
def get_min(self):
return self.stack[-1][1]In the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | push, pop, top O(1); get_min O(n): scans every item | O(n): the items |
| Pairs (shown code) | O(1) for every operation: one append, pop or index | O(n): one extra number per item, about twice the brute force |
Edge cases
- The example sequence (push 5, 3, 7, then min, pop, push 2, min, pop, pop, min): gives 3, then 2, then 5, matching the expected output.
- Duplicate minimums (push 2, push 2, pop): the remaining pair still stores 2, so
get_minis 2. Each copy has its own stored minimum. - Extreme values (−2^31 and 2^31 − 1): returns −2147483648; Python integers have no overflow.
- Calls on an empty stack:
pop,topandget_minall raiseIndexError. LeetCode promises these are only called when the stack is non-empty, so the shown code does not check. - Pop does not return a value in the shown code. Read
top()first if you need the value.
Common mistakes
- Keeping a single
self.minvariable. After the minimum is popped there is no way to know the next smallest without a scan. - Comparing the new value with the top's value instead of the top's stored minimum: after pushing 1, 5, 3 it reports 3 instead of 1.
- In the two-stack version (below), pushing onto the min stack only when
x < mins[-1]. Duplicates of the minimum are then lost after one pop.
The shown code stores a minimum for every item, even when it repeats. Change the design to use a separate stack of minimums that only grows when the minimum changes or repeats. All operations must stay O(1). Describe your approach, then write it if you like.
Compare with our answer
Keep two lists. stack holds every value; mins holds a value only when it is less than or equal to the current minimum. On pop, if the removed value equals the top of mins, pop that too.
class MinStack2:
def __init__(self):
self.stack = []
self.mins = []
def push(self, x):
self.stack.append(x)
if not self.mins or x <= self.mins[-1]:
self.mins.append(x)
def pop(self):
if self.stack.pop() == self.mins[-1]:
self.mins.pop()
def top(self):
return self.stack[-1]
def get_min(self):
return self.mins[-1]
Pushing 5, 6, 7, 8 stores only one minimum. The worst case (decreasing values) is still O(n) extra space, but typical inputs use less.
A strong answer mentions: why <= is needed (push 2, push 2, pop must still have a 2 in mins), that every operation remains O(1), and that the worst-case space is unchanged.
1. A text editor needs undo (remove the latest edit) and must show, in O(1), the largest file size reached by the edits still applied. Which design fits best?
Undo removes from one end, so storing "max so far" with each entry restores the old maximum automatically. A single variable cannot recover after the maximum is undone, and a sorted list or max scan is not O(1).
2. After pop(), why does the shown code not need to recompute the minimum?
Each pair's stored minimum covers that item and everything below it, which is exactly the stack after the items above it are popped. Nothing is searched, and Python lists do not reorder themselves.
3. A learner writes low = min(x, self.stack[-1][0]). After which pushes does get_min() return a wrong value?
Index 0 is the top's value, not its stored minimum, so pushing 3 compares it with 5 and stores 3. In the other orders the true minimum is the latest value pushed or every value is equal, so the bug does not show.
Score 60% or more and the lesson is marked complete.