MediumBlind75StackDesign
Min Stack
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Examples
Input
['MinStack','push','push','push','getMin','pop','top','getMin'] [[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
MinStack stack = [-2, 0, -3]; getMin() returns -3; pop() removes -3; top() returns 0; getMin() returns -2.
Constraints
- •
-2^31 <= val <= 2^31 - 1 - •
Methods pop, top and getMin operations will always be called on non-empty stacks. - •
At most 3 * 10^4 calls will be made to push, pop, top, and getMin.
Approaches
Use two stacks: one for all elements and one to track the minimum at each level.
CodeT: O(1) per operation | S: O(n)
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val):
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]:
self.min_stack.pop()
def top(self):
return self.stack[-1]
def getMin(self):
return self.min_stack[-1]Store (value, current_min) pairs in a single stack.
CodeT: O(1) per operation | S: O(n)
class MinStack:
def __init__(self):
self.stack = []
def push(self, val):
current_min = min(val, self.stack[-1][1] if self.stack else val)
self.stack.append((val, current_min))
def pop(self):
return self.stack.pop()[0]
def top(self):
return self.stack[-1][0]
def getMin(self):
return self.stack[-1][1]Store the difference between current value and minimum.
Diagram
push(-2): stack=[0], min=-2
push(0): stack=[0, 2], min=-2
push(-3): stack=[0, 2, -1], min=-3
getMin(): returns -3
CodeT: O(1) per operation | S: O(n)
class MinStack:
def __init__(self):
self.stack = []
self.min_val = None
def push(self, val):
if not self.stack:
self.stack.append(0)
self.min_val = val
else:
self.stack.append(val - self.min_val)
if val < self.min_val:
self.min_val = val
def pop(self):
if not self.stack:
return
top = self.stack.pop()
if top < 0:
self.min_val = self.min_val - top
def top(self):
top = self.stack[-1]
if top < 0:
return self.min_val
return self.min_val + top
def getMin(self):
return self.min_valComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Two Stacks | O(1) per operation | O(n) | Use two stacks: one for all elements and one to track the minimum at each level. |
| Single Stack with Pairs | O(1) per operation | O(n) | Store (value, current_min) pairs in a single stack. |
| Delta Encoding | O(1) per operation | O(n) | Store the difference between current value and minimum. |
Two Stacks
T: O(1) per operationS: O(n)
Use two stacks: one for all elements and one to track the minimum at each level.
Single Stack with Pairs
T: O(1) per operationS: O(n)
Store (value, current_min) pairs in a single stack.
Delta Encoding
T: O(1) per operationS: O(n)
Store the difference between current value and minimum.
Common Mistakes
Not storing the minimum at each level of the stack
Using the wrong comparison when pushing to min_stack
Not updating min_val correctly when popping the minimum element