155. Min Stack

class MinStack:

    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        

    def push(self, val: int) -> None:
        self.stack1.append(val)
        if not self.stack2 or val <= self.stack2[-1]:
            self.stack2.append(val)
        

    def pop(self) -> None:
        if self.stack2[-1] == self.stack1[-1]:
            self.stack2.pop()
        self.stack1.pop()
        

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

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




Time: o(1)
space: o(n)


class MinStack:

    def __init__(self):
        self.arr = []

    def push(self, x: int) -> None:
        if self.arr:
            self.arr.append((x,min(x,self.getMin())))
        else:
            self.arr.append((x,x))
        

    def pop(self) -> None:
        if self.arr:
            self.arr.pop()
        

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

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