Stack with push, pop, getMin, getMax in O(1)
Filed under Amazon
Free read 2 of 3Confirm that all standard stack operations must be supported alongside min and max queries in O(1).
The question
Design a custom stack data structure that supports push, pop, getMin, and getMax operations, all operating in O(1) time complexity.
Constraints
- All operations (push, pop, getMin, getMax) must run in O(1) time.
- Methods will be called on non-empty stacks where applicable.
Examples
- Input
- push(3), push(1), push(5), getMin(), getMax()
- Output
- getMin() -> 1, getMax() -> 5
- Why
- Maintains tracking structures to return minimum and maximum elements in constant time.
Approach
Confirm that all standard stack operations must be supported alongside min and max queries in O(1).
Use a standard list for the stack and iterate through all elements on every call to getMin or getMax, taking O(N) time.
Maintain auxiliary stacks alongside the main stack: one auxiliary stack to track the current minimum at each level, and another to track the current maximum.
Handling operations on an empty stack or pushing a single element.
Solution
O(1) time for all operations, O(N) space
class MinMaxStack:
def __init__(self):
self.stack = []
self.min_stack = []
self.max_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)
if not self.max_stack or val >= self.max_stack[-1]: self.max_stack.append(val)
def pop(self):
val = self.stack.pop()
if val == self.min_stack[-1]: self.min_stack.pop()
if val == self.max_stack[-1]: self.max_stack.pop()
return val
def getMin(self): return self.min_stack[-1]
def getMax(self): return self.max_stack[-1]
Tips
- What they are testing: Test with duplicate values and descending/ascending insertion sequences.
- Common mistake: Failing to update min and max stacks correctly during pop operations when duplicate minimum or maximum values are removed.
Related Amazon questions
Collected from public candidate posts and coding forums. Updated Nov 2026.