1. One-Liner
Maintain a parallel stack of current minimums so getMin reads the auxiliary top in O(1) alongside normal stack ops.
2. The Problem It Solves
Needed for sliding minima history, range queries on stack order, and design interview fundamentals.
3. The Core Idea
On push x, push min(x, aux.top or x); on pop, pop both stacks together—history stays synchronized.
4. How It Works (Step-by-Step)
| Step | Action |
|---|---|
| 1 | Main stack s, min-stack m |
| 2 | push: s.push(x); m.push(min(x,m.top or x)) |
| 3 | pop: both pop |
| 4 | getMin: m.top |
5. Dry Run Example
Push 5,1,3: mins [5,1,1]—pops restore prior min correctly.
6. Key Properties
| Property | Detail |
|---|---|
| Duplicate mins | Store counts variant possible |
| Space | O(n) worst for min stack |
| Alternative | Store deltas with one stack |
7. Where It Is Used
| Domain / System | Use |
|---|---|
| IDE undo | Min so far |
| Finance | Running min trades |
| Games | Score stacks |
8. Interview Tips
Mention one-stack delta trick if asked to save space; min heap is wrong for LIFO order.
9. Comparison with Other Algorithms
| Technique | Notes |
|---|---|
| Heap | Not stack-ordered |
| Segment tree | Overkill |
| Rescan | O(n) per query |
10. Complexity
| -- | -- |
|---|---|
| Time | O(1) each op |
| Space | O(n) |
Implementation Example (PYTHON)
class MinStack:
def __init__(self):
self.s = []
self.m = []
def push(self, x):
self.s.append(x)
self.m.append(x if not self.m else min(x, self.m[-1]))
def pop(self): self.s.pop(); self.m.pop()
def top(self): return self.s[-1]
def getMin(self): return self.m[-1]