The problem
Design a stack — a pile where you add to and remove from the top — that can also report its smallest element at any moment.
Implement MinStack with push(val) to add a value, pop() to remove the top, top() to read the top, and getMin() to return the smallest value currently in the stack. Every operation must take constant time.
Examples
- Input
["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"] [[], [-2], [0], [-3], [], [], [], []]
- Output
[null, null, null, null, -3, null, 0, -2]
Constraints
- −2³¹ ≤ val ≤ 2³¹ − 1
pop,topandgetMinare only called on a non-empty stack.- At most 3 × 10⁴ calls in total.
The idea
The minimum only changes when something is pushed or popped, and a pop always removes the newest thing. So each entry can carry, alongside its value, “the smallest value from here down”.
Pushing v stores (v, min(v, the minimum below it)). Popping removes the pair, and the pair underneath still knows its own minimum. getMin just reads the top pair.
- Time
- O(1) for every operation
- Space
- O(n) — one pair per element
Solution · every language run against every case
class MinStack: def __init__(self): self.stack = [] # each entry: (value, smallest value at or below it) def push(self, val: int) -> None: smallest = min(val, self.stack[-1][1]) if self.stack else val self.stack.append((val, smallest)) def pop(self) -> None: self.stack.pop() def top(self) -> int: return self.stack[-1][0] def getMin(self) -> int: return self.stack[-1][1]