Max Stack using one stack
Filed under Goldman Sachs
Free read 2 of 3Confirm that the interviewer specifically requires optimizing space down to one stack instead of the standard auxiliary max stack approach.
The question
Implement a stack that supports push, pop, top, and retrieving the maximum element in constant time, using only one underlying stack to optimize space.
Constraints
- All operations (`push`, `pop`, `top`, `getMax`) must run in $O(1)$ time complexity.
- Must use only one underlying stack data structure.
Examples
- Input
- operations: push(-2), push(0), push(-3), getMax(), pop(), top(), getMax()
- Output
- [-3, 0, -2]
- Why
- Max tracks the current maximum value efficiently using a single stack encoding strategy.
Approach
Confirm that the interviewer specifically requires optimizing space down to one stack instead of the standard auxiliary max stack approach.
Iterate through the stack every time `getMax()` is called to find the maximum element, taking $O(N)$ time.
Maintain a variable `min_max` storing the current maximum. When a new value greater than `min_max` is pushed, push `2 * val - min_max` to encode the old maximum, and update `min_max = val`.
Pushing negative numbers and handling the first element pushed into an empty stack.
Solution
O(1) time for all operations, O(N) space
class MaxStack:
def __init__(self):
self.stack = []
self.max_val = None
def push(self, val: int):
if not self.stack:
self.stack.append(val)
self.max_val = val
elif val < self.max_val:
self.stack.append(val)
else:
self.stack.append(2 * val - self.max_val)
self.max_val = val
def pop(self):
if not self.stack:
return
top = self.stack.pop()
if top > self.max_val:
self.max_val = 2 * self.max_val - top
def top(self) -> int:
t = self.stack[-1]
return self.max_val if t > self.max_val else t
def getMax(self) -> int:
return self.max_val
Tips
- What they are testing: Test with strictly increasing and decreasing sequences of numbers to ensure the maximum tracking mechanism handles updates correctly.
- Common mistake: When pushing a new maximum, forgetting to store the previous maximum so that it can be restored when the current maximum is popped.
Related Goldman Sachs questions
Collected from public candidate posts and coding forums. Updated Nov 2026.