Write a class MinStack, a stack of integers with four methods:
push(val)putsvalon top.pop()removes the top item.top()returns the top item.getMin()returns the smallest item currently on the stack.
Every method must take constant time, so getMin can't search the stack. pop, top and
getMin are only called when the stack isn't empty.
Each test is a list of calls, starting with the constructor; the expected answer lists what each
call returns (null for the constructor and for methods that return nothing).
Example 1
- Calls
- MinStack(), push(5), push(2), push(8), getMin(), pop(), top(), getMin()
- Returns
- [null, null, null, null, 2, null, 2, 2]
Example 2
- Calls
- MinStack(), push(3), push(1), pop(), getMin()
- Returns
- [null, null, null, null, 3]
Constraints
- Values are between −2³¹ and 2³¹ − 1.
- A test makes at most 3 × 10⁴ calls.
Show the pattern
Stack
The minimum can only change when you push or pop, and popping restores the minimum from before that push. Remembering the minimum alongside each item, stack-style, keeps every answer at hand.
See stack in a visualiserShow the approach
Keep one stack of pairs (value, minimum so far). Pushing x stores (x, min(x, current minimum));
the current minimum is the top pair's second half. Popping removes a pair, which brings back the
previous minimum automatically. Every method touches only the top.
Time: O(1) per call · Space: O(n)