MinStack

https://www.geeksforgeeks.org/design-a-stack-that-supports-getmin-in-o1-time-and-o1-extra-space/?ref=rp

Two approaches:
1. using two stacks, space complexity: O(n) + O(n) for two stacks, can be reduced to O(n) for original and O(min values) for storing min
2. BEST APPROACH: Using single stack, space complexity: O(n) or O(1) only one stack. For Algo, check push and pop operations, detailed explanation
   is only present at the above provided link.
   
Algo:

A new approach is discussed that supports minimum with O(1) extra space. We define a variable minEle that stores the current minimum element in the stack. Now the interesting part is, how to handle the case when minimum element is removed. To handle this, we push “2x – minEle” into the stack instead of x so that previous minimum element can be retrieved using current minEle and its value stored in stack. Below are detailed steps and explanation of working.

Push(x) : Inserts x at the top of stack.

If stack is empty, insert x into the stack and make minEle equal to x.
If stack is not empty, compare x with minEle. Two cases arise:
If x is greater than or equal to minEle, simply insert x.
If x is less than minEle, insert (2*x – minEle) into the stack and make minEle equal to x. For example, let previous minEle was 3. Now we want to insert 2. We update minEle as 2 and insert 2*2 – 3 = 1 into the stack.
Pop() : Removes an element from top of stack.

Remove element from top. Let the removed element be y. Two cases arise:
If y is greater than or equal to minEle, the minimum element in the stack is still minEle.
If y is less than minEle, the minimum element now becomes (2*minEle – y), so update (minEle = 2*minEle – y). This is where we retrieve previous minimum from current minimum and its value in stack. For example, let the element to be removed be 1 and minEle be 2. We remove 1 and update minEle as 2*2 – 1 = 3.

Important Points:

Stack doesn’t hold actual value of an element if it is minimum so far.
Actual minimum element is always stored in minEle

Implementation/CODE:

class MinStack:
    from math import inf
    def __init__(self):
        """
        initialize your data structure here.
        """
        self.stack_min = list()
        self.stack = list()
        self.min_ = inf
        

    def push(self, x: int) -> None:
        if len(self.stack)==0:
            self.stack.append(x)
            self.min_ = x
        else:
            if self.min_>x:
                # print('self.min_:, x:', self.min_, x)
                temp = 2*x - self.min_
                self.min_ = x
                # print('2, self.min_:, temp:', self.min_, temp)
                x = temp
                # x, self.min_ = 2*x - self.min_, x
            
            self.stack.append(x)
        # print("PUSH(), self.stack:{}, self.min_:{}, x:{}".format(self.stack, self.min_, x))
        
        """
        self.stack.append(x)
        if len(self.stack_min):
            self.stack_min.append(min(self.stack_min[-1], x))
        else:
            self.stack_min.append(x)
        # print("self.stack:{}, self.stack_min:{}, x:{}, self.min_:{}".format(self.stack, self.stack_min, x, self.min_))
        """
        
        

    def pop(self) -> None:
        pop = self.stack.pop()
        if pop<self.min_:
            self.min_ = 2*self.min_ - pop
        # print("POP(), pop:{}, self.min_:{}, self.stack:{}".format(pop, self.min_, self.stack))
        
        """
        if len(self.stack):
            self.stack.pop()
            self.stack_min.pop()
            # print("POP(), self.stack:{}, self.stack_min:{}".format(self.stack, self.stack_min))
        else:
            return
        """
        

    def top(self) -> int:
        if len(self.stack):
            # print("TOP(), self.stack:{}, self.min_:{}".format(self.stack, self.min_))
            if self.stack[-1]<self.min_:
                return (self.min_)
            else:
                return self.stack[-1]
        """
        if len(self.stack):
            print("TOP(), self.stack[-1]:{}".format(self.stack[-1]))
            return self.stack[-1]
        """
        

    def getMin(self) -> int:
        # print("GETMIN(), self.min_:{}, self.stack:{}".format(self.min_, self.stack))
        return self.min_
        """
        if len(self.stack_min):
            # print("getMIN(), self.stack_min[-1]:{}".format(self.stack_min[-1]))
            return self.stack_min[-1]
        """