Min Stack
Task example: Min Stack
Build a MinStack class. push(val) adds a value, pop() removes the latest value, top() reads it, and getMin() returns the smallest stored value. The target is O(1) time per operation. Calls to pop, top, and getMin use a nonempty stack.
push(-2), push(0), push(-3), getMin(), pop(), top(), getMin() → [None, None, None, -3, None, 0, -2]
After removing -3, the top is 0 but the minimum is -2. Reading top or minimum must not change the stack. push and pop return None.
Source task: LeetCode 155Scan for the minimum: video explanation
push(-2), push(0), push(-3), getMin(), pop(), top(), getMin() → [None, None, None, -3, None, 0, -2]
Prefer reading? Follow the steps below.
- Store values in a list. push appends to the end; pop removes from the end; top reads the last item. Each instance has its own list.
- getMin scans the current list with min. It returns the right value, including duplicates and negatives, but repeats the scan for every query.
- This baseline does not meet the constant-time getMin requirement. Do not sort the list: sorting changes which value is on top.
Time complexity · O(n) getMin
With n stored values, getMin scans n items: O(n). top is O(1); Python list push and pop are amortized O(1).
Space complexity · O(n)
O(n) total storage for the stack. The minimum scan itself needs O(1) additional working space.
Minimum snapshots: video explanation
push(-2), push(0), push(-3), getMin(), pop(), top(), getMin() → [None, None, None, -3, None, 0, -2]
Prefer reading? Follow the steps below.
- Store (value, minimum_so_far) at every depth. On push, compare the new value with the previous minimum; on an empty stack, use the value itself.
- pop removes the entire pair. top reads field 0; getMin reads field 1. Removing a pair automatically restores the minimum saved at the previous depth.
- Duplicate minima are safe: push 2, 1, 1. After one pop the minimum is still 1; after another pop it is 2. Each pair stores the minimum at or below it.
Minimum queries improve from O(n) to O(1). Both approaches use O(n) total storage; a second field changes only the constant factor.
Time complexity · O(1) queries
top and getMin are O(1). push and pop do constant work, with amortized O(1) time for Python list resizing.
Space complexity · O(n)
O(n) total storage for n pairs. No full-stack copy or scan is needed for a query.