Problem Description
Welcome to another fun coding challenge! Today, we'll be tackling the Min Stack problem.
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Remove the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
That's it! Now, let's dive into the solution.
Solution
We'll start by creating a stack class that contains a list and a minimum value. The list will hold the values that are pushed onto the stack, while the minimum value will keep track of the minimum value seen so far.
class MinStack:
def __init__(self):
self.stack = []
self.min_val = float('inf')
We'll then implement the push() method, which adds an element to the top of the stack. If the element being pushed is less than or equal to the current minimum value, we'll update the minimum value.
def push(self, x: int) -> None:
self.stack.append(x)
if x <= self.min_val:
self.min_val = x
Next, we'll implement the pop() method, which removes the element on top of the stack. If the element being popped is the minimum value, we'll need to update the minimum value to the next smallest value on the stack.
def pop(self) -> None:
if self.stack.pop() == self.min_val:
self.min_val = min(self.stack) if self.stack else float('inf')
The pop() method first removes the top element from the stack using the pop() method. If the popped element is the minimum value, we'll need to update the minimum value. We'll check if the popped element is equal to the current minimum value, and if it is, we'll update the minimum value to the smallest value on the stack (if the stack is not empty) or float('inf') (if the stack is empty).
Next, we'll implement the top() method, which returns the top element of the stack. This method is straightforward, as it simply returns the last element of the stack.
def top(self) -> int:
return self.stack[-1]
Finally, we'll implement the getMin() method, which returns the minimum value in the stack. This method is also straightforward, as we've been keeping track of the minimum value as we push and pop elements from the stack.
def getMin(self) -> int:
return self.min_val
And there you have it! Here's the full code for our MinStack class:
class MinStack:
def __init__(self):
self.stack = []
self.min_val = float('inf')
def push(self, x: int) -> None:
self.stack.append(x)
if x <= self.min_val:
self.min_val = x
def pop(self) -> None:
if self.stack.pop() == self.min_val:
self.min_val = min(self.stack) if self.stack else float('inf')
def top(self) -> int:
return self.stack[-1]
def getMin(self) -> int:
return self.min_val
Complexity Analysis
Now that we have our solution, let's analyze its time and space complexity.
Time Complexity
Our push(), pop(), top(), and getMin() methods all have a time complexity of O(1), as they all perform constant time operations on the stack.
Space Complexity
Our MinStack class uses a list to store the values pushed onto the stack, and a variable to store the minimum value seen so far. Therefore, the space complexity of our class is O(n), where n is the number of elements pushed onto the stack.
Conclusion
And there you have it! We've successfully tackled the Min Stack problem. I hope you found this blog post helpful and informative. Happy Coding! 😎
