LeetMotion
Design a stack that supports push, pop, top, and getMin — all in O(1) time. The catch: getMinmust return the current minimum element in the stack at any moment, even as elements are pushed and popped.
-2³¹ ≤ val ≤ 2³¹ - 1pop, top, getMin always called on a non-empty stackThe hard part isn't push, pop, or top — a regular stack does all three in O(1). The hard part is getMin. After popping the current minimum, what is the new minimum? You can't scan the whole stack in O(1).
The key insight: track the minimum at every level of the stack. When you push a value, also record what the minimum is at that point. When you pop, you pop that recorded minimum too. The top of the min-tracker is always the current minimum — no scanning needed.
No extra storage. When getMin is called, evacuate the entire stack into a temp list while tracking the smallest value seen, then put everything back.
def getMin(self) -> int:
tmp = []
mini = self.stack[-1]
while self.stack:
mini = min(mini, self.stack[-1])
tmp.append(self.stack.pop())
while tmp:
self.stack.append(tmp.pop())
return miniWorks, but every getMin call is O(n). The constraint explicitly says O(1). This approach fails the problem requirements.
Keep a parallel minStack. On every push, compute the new running minimum and push it there too. On every pop, pop from both. The top of minStack is always the current minimum.
class MinStack:
def __init__(self):
self.stack = []
self.minStack = []
def push(self, val: int) -> None:
self.stack.append(val)
val = min(val, self.minStack[-1] if self.minStack else val)
self.minStack.append(val)
def pop(self) -> None:
self.stack.pop()
self.minStack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.minStack[-1]Every operation is O(1). The tradeoff is O(n) extra space for minStack, which grows at the same rate as stack.
Instead of a second stack, encode the difference between the pushed value and the current minimum. A negative encoded value signals a new minimum was set. On pop, decode it to restore the previous minimum.
class MinStack:
def __init__(self):
self.min = float('inf')
self.stack = []
def push(self, val: int) -> None:
if not self.stack:
self.stack.append(0)
self.min = val
else:
self.stack.append(val - self.min)
if val < self.min:
self.min = val
def pop(self) -> None:
pop = self.stack.pop()
if pop < 0:
self.min = self.min - pop # restore previous min
def top(self) -> int:
top = self.stack[-1]
return self.min if top <= 0 else top + self.min
def getMin(self) -> int:
return self.minval - min can overflow 32-bit integers. The two-stack solution is clearer and almost always preferred. Know this exists; reach for two stacks by default.| Approach | Time | Space | Notes |
|---|---|---|---|
| Brute Force | O(n) getMin | O(1) extra | Fails the O(1) constraint |
| Two Stacks | O(1) all | O(n) | Simple, safe, recommended |
| One Stack (encoded) | O(1) all | O(n) | Overflow risk with 32-bit ints |
Min Stack is the template for augmented data structures — you take a standard structure and add a second structure that answers a "running query" in O(1) by shadowing every update.
maxStack tracks running maximum. Identical approach.A common "optimization" is to only push to minStack when the new value is smaller than the current minimum. This saves space but breaks synchronization: when you pop from stack, you don't know whether to pop from minStack. Keep them in sync — push and pop both stacks on every operation.
Storing val - min overflows when val = Integer.MIN_VALUEand min = Integer.MAX_VALUE. Use long in Java or just use the two-stack approach which has no arithmetic at all.
The problem guarantees this won't happen in valid test cases, but your implementation should still be coherent. Accessing minStack[-1] on an empty list throws an error. In interviews, acknowledge the constraint but don't add defensive code that muddies the solution.
Discussion
…