Day 10: Min Stack - leetcode - Python3

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 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 and getMin operations will always be called on non-empty stacks.
• At most 3 * 104 calls will be made to push, pop, top, and getMin.

SOLUTION:

class MinStack:

    def __init__(self):

        self.stack=[]

        self.min_stack=[]

    def push(self, val: int) -> None:

        self.stack.append(val)

        val= min(val, self.min_stack[-1] if self.min_stack else val)

        self.min_stack.append(val)

    def pop(self) -> None:

        if  self.stack:

            self.stack.pop()

        if self.min_stack:

            self.min_stack.pop()

    def top(self) -> int:

        if  self.stack:

            return self.stack[-1]

    def getMin(self) -> int:

        return self.min_stack[-1]

# Your MinStack object will be instantiated and called as such:

# obj = MinStack()

# obj.push(val)

# obj.pop()

# param_3 = obj.top()

# param_4 = obj.getMin()

Time Complexity:

The time complexity of the push, pop, top, and getMin methods is O(1), which means they have constant time complexity.

The code implements a MinStack class that supports the following operations: push(), pop(), top(), and getMin().

1. The __init__(self) method initializes the MinStack object. It creates two empty lists, self.stack and self.min_stack, which will be used to store the elements of the stack and the minimum values, respectively.

2. The push(self, val: int) -> None method is used to push an element val onto the stack. It appends the val to the self.stack list. Then, it determines the minimum value by comparing val with the current minimum value stored in self.min_stack[-1] (if self.min_stack is not empty). If self.min_stack is empty, it means the pushed value is the first element, so it assigns val as the minimum value. The minimum value is then appended to self.min_stack.

3. The pop(self) -> None method removes the top element from the stack. It uses the pop() method to remove the top element from self.stack. It also removes the corresponding minimum value from self.min_stack using the pop() method.

4. The top(self) -> int method returns the top element of the stack without modifying the stack. It uses the index -1 to access the last element in self.stack and returns it.

5. The getMin(self) -> int method retrieves the minimum element in the stack. It uses the index -1 to access the last element in self.min_stack and returns it.