155. Min Stack — LeetCode(Python)
I got you!
Problem:
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 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 getMin()
retrieves the minimum element in the stack.
You must implement a solution with O(1)
time complexity for each function.
Example 1:
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
Constraints:
-231 <= val <= 231 - 1
- Methods
pop
,top
andgetMin
operations will always be called on non-empty stacks. - At most
3 * 104
calls will be made topush
,pop
,top
, andgetMin
.
Solution:
class MinStack:def __init__(self):
self.stack = []
self.min_val = []
def push(self, val: int) -> None:
self.stack += [val]
if self.min_val:
self.min_val += [min(val, self.min_val[-1])]
else:
self.min_val += [val]def pop(self) -> None:
self.stack = self.stack[:-1]
self.min_val = self.min_val[:-1]def top(self) -> int:
return self.stack[-1]def getMin(self) -> int:
return self.min_val[-1]
Explanation —
This is a simple implementation of the Stack Abstract Data Type (ADT).
While implementing basic functionalities of the stack, we also keep a min_val stack that stores the minimum value in the stack at a given point in time.
Everytime we push a new element onto the stack, we update our min_val.
And everytime we pop an element from the stack, we do the same for our min_val stack as well.
Time and Space Complexity —
All member functions in our class perform constant time operations.
And, since we are using a different stack to keep track of the minimum value in our stack, our code requires a linear amount of extra space.
Thus, if n elements are going to be pushed onto the stack,
Time Complexity: O(1)
Space Complexity: O(n)