Stack with push, pop, and getMax all in O(1)
Implement a collection with three operations, each O(1): push(value) adds an element, pop() removes the most recently added one, and getMax() returns the current maximum among all stored elements.
Constraints:
- every operation must be
O(1), notO(n)— no scanning ongetMax getMaxmust stay correct after the current maximum is popped
class MaxStack {
void push(int value) { /* your code here */ }
int pop() { /* your code here */ }
int getMax() { /* your code here */ }
}Write the implementation.
Keep two stacks. The main stack holds the values; a second max stack holds, at each level, the maximum of everything pushed so far. On push, also push max(value, maxStack.peek()) onto the max stack. On pop, pop both. getMax returns maxStack.peek(). Because the maximum is recomputed and stored per element, it stays correct after a pop, and all three operations are O(1).
- ✗Caching a single max value that becomes wrong once it is popped
- ✗Reaching for a sorted structure whose operations are not actually
O(1) - ✗Scanning the elements in
getMax, making itO(n)
- →Why does a single cached max value break after a pop, but the paired stack does not?
- →How would you extend this to return the minimum in
O(1)as well?
Solution
class MaxStack {
private final Deque<Integer> data = new ArrayDeque<>();
private final Deque<Integer> max = new ArrayDeque<>(); // max at each level
void push(int value) {
data.push(value);
max.push(max.isEmpty() ? value : Math.max(value, max.peek()));
}
int pop() {
max.pop();
return data.pop();
}
int getMax() { return max.peek(); }
}Idea. The second stack stores "the running maximum as of this push". After each push the top of max is the maximum of every element in the stack. When an element is popped, its matching max entry is popped too, so the top again reflects the maximum of what remains.
A single cached maximum does not work: once it is popped, you cannot know the next-largest without scanning. The paired stack stores the history of maxima, so every operation is O(1) and getMax stays correct after any pop.
