Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Implement the MinStack
class:
MinStack()
initializes the stack object.void push(int val)
pushes the element val
onto the stack.void pop()
removes the element on the top of the stack.int top()
gets the top element of the stack.int getMin()
retrieves the minimum element in the stack.You must implement a solution with O(1)
time complexity for each function.
Example:
Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]
Output
[null,null,null,null,-3,null,0,-2]
Explanation
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2
This problem requires designing a stack data structure with the additional functionality of retrieving the minimum element in O(1) time complexity.
A straightforward approach is to use a standard stack to store the elements and, when getMin()
is called, iterate through the entire stack to find the minimum element. This approach is simple to implement but doesn't meet the O(1) time complexity requirement for getMin()
.
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 getMin(self) -> int:
if not self.stack:
return None # Or handle empty case appropriately
return min(self.stack)
push()
: O(1)pop()
: O(1)top()
: O(1)getMin()
: O(n), where n is the number of elements in the stack.To achieve O(1) time complexity for getMin()
, we can use an auxiliary stack to keep track of the minimum elements. This auxiliary stack will store the minimum element seen so far whenever a new element is pushed onto the main stack.
push(val)
:
val
onto the main stack.val
is less than or equal to the current minimum (top of the auxiliary stack), push val
onto the auxiliary stack.pop()
:
top()
:
getMin()
:
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[-1] == self.min_stack[-1]:
self.min_stack.pop()
self.stack.pop()
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_stack[-1]
push()
: O(1)pop()
: O(1)top()
: O(1)getMin()
: O(1)getMin()
or top()
is called, you can either return None
or raise an exception, as stated in the problem description, these methods will always be called on non-empty stacks.Instead of using an auxiliary stack that could take O(N) space, we could track the minimum value and store the difference between the current value and the minimum value.
push(val)
:
pop()
:
top()
:
getMin()
:
class MinStack:
def __init__(self):
self.stack = []
self.min_val = None
def push(self, val: int) -> None:
if not self.stack:
self.min_val = val
self.stack.append(0)
else:
diff = val - self.min_val
self.stack.append(diff)
if diff < 0:
self.min_val = val
def pop(self) -> None:
diff = self.stack.pop()
if diff < 0:
self.min_val = self.min_val - diff
def top(self) -> int:
diff = self.stack[-1]
if diff > 0:
return self.min_val + diff
else:
return self.min_val
def getMin(self) -> int:
return self.min_val
push()
: O(1)pop()
: O(1)top()
: O(1)getMin()
: O(1)