Minimum Stack
Problem Statement
Design a stack class that supports the push
, pop
, top
, and get_min
operations.
MinStack()
initializes the stack object.void push(int val)
pushes the elementval
onto the stack.void pop()
removes the element on the top of the stack.int top()
gets the top element of the stack.int get_min()
retrieves the minimum element in the stack.
Each function should run in O(1)
time.
Example 1:
Input: ["MinStack", "push", 1, "push", 2, "push", 0, "get_min", "pop", "top", "get_min"]
Output: [None, None, None, None, 0, None, 2, 1]
Explanation:min_stack = MinStack()min_stack.push(1)min_stack.push(2)min_stack.push(0)min_stack.get_min() # return 0min_stack.pop()min_stack.top() # return 2min_stack.get_min() # return 1
Constraints:
-2^{31} <= val <= 2^{31} - 1
pop
,top
andget_min
will always be called on non-empty stacks.
You should aim for a solution with O(1)
time for each function call and O(n)
space, where n
is the maximum number of elements present in the stack.
Recommended Time and Space Complexity
You should aim for a solution with O(1)
time for each function call and O(n)
space, where n
is the maximum number of elements present in the stack.
Hint 1
A brute force solution would be to always check for the minimum element in the stack for the getMin()
function call. This would be an O(n)
approach. Can you think of a better way? Maybe O(n)
extra space to store some information.
Hint 2
We can use a stack to maintain the elements. But how can we find the minimum element at any given time? Perhaps we should consider a prefix approach.
Hint 3
We use an additional stack to maintain the prefix minimum element. When popping elements from the main stack, we should also pop from this extra stack. However, when pushing onto the extra stack, we should push the minimum of the top element of the extra stack and the current element onto this extra stack.
Solution
Brute Force
class MinStack: def __init__(self): self.stack = []
def push(self, val: int) -> None: self.stack.append(val)
def pop(self) -> None: self.stack.pop()
def top(self) -> int: return self.stack[-1]
def get_min(self) -> int: temp_stack = [] min_val = self.stack[-1]
while self.stack: min_val = min(min_val, self.stack[-1]) temp_stack.append(self.stack.pop())
while temp_stack: self.stack.append(temp_stack.pop())
return min_val
Time complexity: O(n)
for get_min()
and O(1)
for other operations. Space complexity: O(n)
for get_min()
and O(1)
for other operations.