Minimum Stack

https://neetcode.io/problems/minimum-stack?list=neetcode150

Design a stack class that supports the push, pop, top, and getMin operations.

• 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.

Each function should run in $O(1)$ time.

Constraints:

• -2^31 <= val <= 2^31 - 1.
• pop, top and getMin will always be called on non-empty stacks.

class MinStack:
 
    def __init__(self):
        self._stack: list[int] = []
		# NOTE: We use another stack `_min_history` to track the minimum of
		# corresponding substack. This is possible because only the top of 
		# the stack is modified through `push` and `pop`.
        self._min_history: list[int] = []
 
    def push(self, val: int) -> None:
        self._stack.append(val)
 
		if len(self._min_history) == 0:  # CASE: Stack is empty
			self._min_history.append(val)
			return
 
        latest_min = self._min_history[-1]
        if val < latest_min:  # CASE: `val` is minimum of current stack
            self._min_history.append(val)
        else:
            self._min_history.append(latest_min)
 
    def pop(self) -> None:
        _ = self._stack.pop()
        _ = self._min_history.pop()
 
    def top(self) -> int:
        return self._stack[-1]
        
    def getMin(self) -> int:
        return self._min_history[-1]