155. Min Stack (Design + Stack) 20.3.30 Easy

Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
Example:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> Returns -3.
minStack.pop();
minStack.top();      --> Returns 0.
minStack.getMin();   --> Returns -2.

Solution: ------------------------------------------------------ Design + Stack
---------------------------------------------------------------- O(1) T, O(n) S
class MinStack(object):

    def __init__(self):
        self.stack = []
        """
        initialize your data structure here.
        """
        

    def push(self, x):
        """
        :type x: int
        :rtype: None
        """
        currmin = self.getMin()
        if currmin is None or x < currmin:           # IMPORTANT !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!
                                                     # Can not be "if not currmin", must be "if currmin is None" !!!!!!!!!!!!!!!!!
                                                     # because first statement include the cases when currmin is 0 instead of None
            currmin = x
        self.stack.append((x, currmin))              # Design a tuple to store the current value and current minimum number
                                                     # At each level, there is a current minimum value and we store it in the tuple
                                                     # and for the future, whenever we come to each level, we can access the currmin
                                                     # In this way, we can get a O(1) instead of O(n) in the getMin()
                                                     # Since we may need to go over all element in the stack to find the minimum
        
    def pop(self):
        """
        :rtype: None
        """
        self.stack.pop()

    def top(self):
        """
        :rtype: int
        """
        if self.stack == []: 
            return None
        else:
            return self.stack[-1][0]

    def getMin(self):
        """
        :rtype: int
        """
        if self.stack == []: 
            return None
        else:
            return self.stack[-1][1]

# Your MinStack object will be instantiated and called as such:
# obj = MinStack()
# obj.push(x)
# obj.pop()
# param_3 = obj.top()
# param_4 = obj.getMin()


Java Version:
class MinStack {

    /** initialize your data structure here. */
    Stack<int[]> s = new Stack<>();                         # Must be here !
    public MinStack() {
    }
    
    public void push(int x) {
        int currMin;
        if (s.size() == 0) {
            currMin = x;
        } else {
            if (s.peek()[1] > x) {
                currMin = x;
            } else {
                currMin = s.peek()[1];
            }
        }
        s.add(new int[] {x, currMin});
    }
    
    public void pop() {
        s.pop();
    }
    
    public int top() {
        return s.peek()[0];
    }
    
    public int getMin() {
        return s.peek()[1];
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */