Stack
Store extra state on the way in
Why it matters
APIs sometimes promise both ordinary collection updates and instant aggregate queries. A latency spike appears if getMin quietly scans thousands of current values while every other operation is constant time. For pushes -2, 0, and -3, push, pop, top, and getMin must each remain O(1).
Example
Min Stack
Implement a stack with push, pop, top, and getMin — all O(1). Tests call the driver minStack(ops, args) after you fill in the class.
- Input
- operations = ["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"], arguments = [[], [-2], [0], [-3], [], [], [], []]
- Output
- [None, None, None, None, -3, None, 0, -2]
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Min Stack
operations = ["MinStack", "push", "push", "push", "getMin", "pop", "top", "getMin"], arguments = [[], [-2], [0], [-3], [], [], [], []]→[None, None, None, None, -3, None, 0, -2]
The baseline, Scan for the minimum, is O(n) · O(n). The better model below keeps this exact input and removes that bottleneck.
For pushes -2, 0, and -3, store (-2, -2), (0, -2), and (-3, -3). The extra minimum in each pair lets getMin return -3, then -2 after pop, replacing the brute scan of every current value.
Push -2 as (-2, -2): its second field is the minimum so far. Pushing 0 compares it with -2 and stores (0, -2). Pushing -3 stores (-3, -3). The top pair now answers both top() = -3 and getMin() = -3.
After pop removes (-3, -3), (0, -2) becomes the top pair. Its saved -2 is again the current minimum, so getMin does not scan [-2, 0]. Each entry preserves the aggregate for the exact stack prefix ending there.
Visual anchor
Min Stack
calls
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.