Min Stack
Problem Statement
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Example: push(2), push(0), push(3), push(0), getMin() → 0
Approach 1: Brute Force
Explanation: Store all elements; find min by scanning stack each time.
Time Complexity: push/pop O(1), getMin O(n)
Space Complexity: O(n)
stack = empty
push(x): stack.push(x)
pop(): stack.pop()
top(): return stack[-1]
getMin(): return min(stack)
💡 Think: Scan the whole stack each getMin; simple but slow for queries.
Approach 2: Auxiliary Stack (Better)
Explanation: Maintain an additional stack to track current minimum.
Time Complexity: O(1) for all operations
Space Complexity: O(n)
stack = empty
minStack = empty
push(x):
stack.push(x)
if minStack is empty or x <= minStack.top():
minStack.push(x)
pop():
if stack.pop() == minStack.top():
minStack.pop()
top(): return stack.top()
getMin(): return minStack.top()
💡 Think: Track the running minimum alongside values for O(1) mins.
Approach 3: Single Stack with Encoded Values (Optimal)
Explanation: Use single stack with encoded differences to track minimum.
Time Complexity: O(1)
Space Complexity: O(n)
stack = empty
minVal = ∞
push(x):
if x < minVal:
stack.push(2*x - minVal)
minVal = x
else:
stack.push(x)
pop():
top = stack.pop()
if top < minVal:
minVal = 2*minVal - top
top(): return minVal if top < minVal else top
getMin(): return minVal
💡 Think: Encode pushes to restore previous mins in O(1) space overhead.