155. Min Stack
Model: qwen2.5-coder:14b
Topics: Stack,Design
FAANG asked: 1
Acceptance rate: 46.8%
Problem Breakdown
The problem requires designing a stack that supports standard stack operations (push, pop, top) along with an additional operation getMin which retrieves the minimum element in constant time. The stack should handle integer values within the range of -2^31 to 2^31 - 1. The methods pop, top, and getMin will always be called on non-empty stacks, and there can be up to 3 * 10^4 calls made to these operations.
Inputs:
push(val): An integer value to be pushed onto the stack.pop(): No input; removes the top element of the stack.top(): No input; returns the top element of the stack without removing it.getMin(): No input; retrieves and returns the minimum element in the stack.
Outputs:
push(val),pop(): No output (void).top(): Returns the integer value at the top of the stack.getMin(): Returns the integer value which is the minimum element in the stack.
Implicit Constraints/Edge Cases:
- The stack should support constant time operations for all methods.
- Handling negative numbers and potential overflow scenarios within the given range.
- Ensuring that the stack remains consistent after each operation.
Intuition
A brute-force approach would involve maintaining a standard stack and iterating through it to find the minimum element whenever getMin is called. This approach would result in O(n) time complexity for the getMin operation, which is not efficient enough given the constraints.
The key insight is to maintain an auxiliary data structure that keeps track of the minimum values at each level of the stack. By doing so, we can retrieve the minimum element in constant time. A common approach is to use a second stack where each element represents the current minimum value up to that point in the main stack.
Approach
-
Data Structures:
- Use two stacks:
stackfor storing all elements andmin_stackfor keeping track of the minimum values.
- Use two stacks:
-
Operations:
- Push(val):
- Push the value onto the
stack. - If
min_stackis empty or the current value is less than or equal to the top ofmin_stack, push the value ontomin_stack.
- Push the value onto the
- Pop():
- Pop the value from the
stack. - If the popped value is equal to the top of
min_stack, pop it frommin_stackas well.
- Pop the value from the
- Top():
- Return the top element of the
stack.
- Return the top element of the
- GetMin():
- Return the top element of the
min_stack.
- Return the top element of the
- Push(val):
This approach ensures that all operations are performed in constant time, O(1).
Complexity Analysis
-
Time Complexity:
- All operations (
push,pop,top,getMin) have a time complexity of O(1).
- All operations (
-
Space Complexity:
- The space complexity is O(n) where n is the number of elements pushed onto the stack. This is because we use an additional stack to keep track of minimum values.
Solution
class MinStack:
def __init__(self):
self.stack = []
self.min_stack = []
def push(self, val: int) -> None:
self.stack.append(val)
if not self.min_stack or val <= self.min_stack[-1]:
self.min_stack.append(val)
def pop(self) -> None:
if self.stack.pop() == self.min_stack[-1]:
self.min_stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
Edge Cases Handled
- Empty Stack: The problem constraints ensure that
pop,top, andgetMinare never called on an empty stack, so we don’t need to handle this case. - Negative Numbers: The solution correctly handles negative numbers as it compares values directly without any assumptions about their positivity or negativity.
- Overflow/Underflow: Given the constraints of integer ranges, Python’s list operations inherently handle overflow and underflow scenarios.