Medium
Min Stack
Keep a parallel stack of the minimum-so-far.
Approach
Alongside the main stack, push the current minimum at each step (the smaller of the new value and the previous min). Pop both together. getMin is then the top of the min-stack in O(1), with no scanning.
Time complexity
O(1) per operation
Space complexity
O(n)
Common mistake
Scanning the whole stack for the min on each getMin call — that's O(n) and defeats the purpose.
See it run, step by step
Generate an interactive lesson for Min Stack — trace every variable and watch the algorithm execute until it clicks.
Start a lesson on Min Stack