Description
Implement push, pop, top, and getMin for an integer stack. All operations must take constant time. Calls that read or remove values occur only when the stack is non-empty.
Solution
def create_min_stack():
return []
def push(state, value):
minimum = min(value, state[-1][1]) if state else value
state.append((value, minimum))
def pop(state):
state.pop()
def top(state):
return state[-1][0]
def get_min(state):
return state[-1][1]Examples
Example 1
- Input
[["MinStack"],["push",-2],["push",0],["push",-3],["getMin"],["pop"],["top"],["getMin"]]- Output
[null,null,null,null,-3,null,0,-2]
Removing -3 restores the previous minimum -2.
Example 2
- Input
[["MinStack"],["push",2],["push",2],["pop"],["getMin"]]- Output
[null,null,null,null,2]
A duplicate minimum is still present.
Example 3
- Input
[["MinStack"],["push",7],["top"]]- Output
[null,null,7]
The only value is at the top.
Approach
Store a pair for every pushed value: the value itself and the minimum up to that position. Popping removes both histories together, so the last pair always contains the current minimum.
Time & space
O(1) time per operation and O(n) auxiliary space, where n is the number of stored values.