Min Stack

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

Solution 1: Version 1 (Draft)

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []   
        self.stack_min = []
        self.min = float('Inf')
        
    def push(self, x: int) -> None:
        if self.stack == []:
            self.min = x   
        else:
            self.min = min(self.min, x)
            
        self.stack.append(x)  
        self.stack_min.append(self.min)
            
    def pop(self) -> None:
        del self.stack[-1]
        
        if len(self.stack_min) != 1:
            del self.stack_min[-1]
            self.min = self.stack_min[-1]
        else:
            self.min = self.stack_min[-1]
            del self.stack_min[-1]
    
        
    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.min

Solution 2: Version 2 (Clean)

class MinStack:

    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack = []
        self.stackMin = []
        
    def push(self, x: int) -> None:
        if self.stack == [] or x <= self.stackMin[-1]: #Only possible because Python supports lazy operators.
            self.stackMin.append(x)
        self.stack.append(x)       

    def pop(self) -> None:
        if self.stack != []:
            popped = self.stack[-1]
            del self.stack[-1]
            
            if popped == self.stackMin[-1]:
                del self.stackMin[-1]

    def top(self) -> int:
        return self.stack[-1]

    def getMin(self) -> int:
        return self.stackMin[-1]

Solution 3

class MinStack:

    def __init__(self):
        self.list = []
        self.list_min = []

    def push(self, val: int) -> None:
        self.list.append(val)
        
        if len(self.list_min) == 0:
            self.list_min.append(val)
        else:
            if val <= self.list_min[-1]:
                self.list_min += [val]
            else:
                self.list_min = [val] + self.list_min

    def pop(self) -> None:
        popped = self.list.pop(-1)
        
        if popped == self.list_min[-1]:
            self.list_min.pop(-1)
        else:
            self.list_min.remove(popped)
        
    def top(self) -> int:
        return self.list[-1]

    def getMin(self) -> int:
        return self.list_min[-1]