716. Max Stack
Model: qwen2.5-coder:14b
Topics: Design
FAANG asked: 1
Acceptance rate: 43.1%
Problem Breakdown
We need to design a MaxStack data structure that supports standard stack operations (push, pop, top) along with additional operations to find the maximum element in the stack (peekMax) and remove the maximum element (popMax). The stack should support these operations efficiently.
Inputs:
push(int x): Adds an integerxto the top of the stack.pop(): Removes and returns the top element of the stack.top(): Returns the top element without removing it.peekMax(): Returns the maximum element in the stack without removing it.popMax(): Removes and returns the maximum element from the stack. If there are multiple maximum elements, only the top-most one should be removed.
Outputs:
- The operations return specific values as described above.
Implicit Constraints/Edge Cases:
- The stack can contain negative numbers.
- There will always be at least one element in the stack when
pop,top,peekMax, orpopMaxis called. - At most 10,000 calls will be made to these operations.
Intuition
A brute-force approach would involve maintaining a single list and performing linear scans for peekMax and popMax. This would result in O(n) time complexity for these operations, which is inefficient given the constraints.
The key insight is to use two stacks: one for regular stack operations and another to keep track of the maximum elements. By doing this, we can achieve O(1) time complexity for top and O(log n) for other operations.
Approach
-
Data Structures:
- Use a primary stack (
stack) to store all elements. - Use an auxiliary stack (
max_stack) to keep track of the maximum elements. The top of this stack will always be the current maximum element in thestack.
- Use a primary stack (
-
Operations:
push(int x): Pushxonto the primary stack. Ifxis greater than or equal to the current maximum (top ofmax_stack), push it ontomax_stack.pop(): Pop and return the top element from the primary stack. If this element is equal to the top ofmax_stack, pop it frommax_stackas well.top(): Return the top element of the primary stack without removing it.peekMax(): Return the top element ofmax_stack, which represents the current maximum in the primary stack.popMax(): To remove the maximum element, temporarily pop elements from the primary stack and push them onto a temporary stack until the maximum is found. Then, pop the maximum element. Reinsert all elements from the temporary stack back into the primary stack and updatemax_stackaccordingly.
Complexity Analysis
- Time Complexity:
push,pop,top: O(1)peekMax: O(1)popMax: O(n) in the worst case, but amortized over multiple operations, it can be considered efficient due to the reinsertion of elements.
- Space Complexity: O(n), where n is the number of elements pushed onto the stack. This is due to the storage required for both stacks.
Solution
class MaxStack:
def __init__(self):
self.stack = []
self.max_stack = []
def push(self, x: int) -> None:
self.stack.append(x)
if not self.max_stack or x >= self.max_stack[-1]:
self.max_stack.append(x)
def pop(self) -> int:
val = self.stack.pop()
if val == self.max_stack[-1]:
self.max_stack.pop()
return val
def top(self) -> int:
return self.stack[-1]
def peekMax(self) -> int:
return self.max_stack[-1]
def popMax(self) -> int:
max_val = self.max_stack[-1]
temp = []
while self.stack[-1] != max_val:
temp.append(self.stack.pop())
self.stack.pop() # Remove the max element
self.max_stack.pop()
# Reinsert elements from temp back into stack and update max_stack
for x in reversed(temp):
self.push(x)
return max_val
Edge Cases Handled
- Negative Numbers: The solution correctly handles negative numbers as it compares values without any assumptions.
- Multiple Maximums: When multiple maximum elements exist,
popMaxremoves only the top-most one by design. - Empty Stack Operations: The problem constraints ensure that operations like
pop,top,peekMax, andpopMaxare never called on an empty stack, so these cases do not need to be explicitly handled.