Problem Statement

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

Implement the MinStack class:

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

You must implement a solution with O(1) time complexity for each function.

Additional information

• -2^31 <= val <= 2^31 - 1
• Methods pop, top and getMin operations will always be called on non-empty stacks.
• At most 3 * 10^4 calls will be made to push, pop, top, and getMin.

Example 1:

Input
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

Output
[null,null,null,null,-3,null,0,-2]

Explanation:

• MinStack minStack = new MinStack();
• minStack.push(-2);
• minStack.push(0);
• minStack.push(-3);
• minStack.getMin(); // return -3
• minStack.pop();
• minStack.top(); // return 0
• minStack.getMin(); // return -2

Brute Force (Standard Array & Min Scan)

Intuition

The easiest way to implement a stack in Python is by using a standard List. The append() and pop() methods natively handle adding and removing elements from the end of the list in O(1) time, satisfying the push, pop, and top requirements perfectly.

However, finding the minimum value natively requires scanning the entire list from start to finish.

Algorithm

1. Initialize: Create an empty stack list.
2. push: Append val to self.stack.
3. pop: Pop the last element from self.stack.
4. top: Return the last element self.stack[-1].
5. getMin: Use Python's built-in min() function on self.stack to scan the list and return the smallest value.

class MinStack:
    def __init__(self):
        self.stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)

    def pop(self) -> None:
        self.stack.pop()

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

    def getMin(self) -> int:
        # Scanning the entire array is an O(N) operation
        return min(self.stack)

Time & Space Complexity

• Time complexity:
  • push, pop, top: O(1) time.
  • getMin: O(N) time because it must inspect every element in the stack. This fails the strict O(1) requirement for all methods.
• Space complexity: O(N) where N is the number of elements in the stack.

Parallel Min Stack - Optimal

Intuition

To achieve O(1) time for getMin, we cannot search the stack when the method is called. We must already know the answer!

We can achieve this by maintaining a secondary, parallel stack (let's call it min_stack). Whenever we push a new value onto our main stack, we also push the current historical minimum onto the min_stack.
If the new value is smaller than the current minimum, it becomes the new minimum. If it is larger, we just copy the previous minimum and push it again. This way, the top of min_stack will always tell us the exact minimum value for the current height of the main stack. When we pop from the main stack, we also pop from the min_stack, instantly reverting our "historical minimum" to whatever it was before.

Algorithm

1. Initialize: Create two empty lists: self.stack (for actual values) and self.min_stack (for tracking the minimums).
2. push:
   • Append val to self.stack.
   • If self.min_stack is empty, the new val is definitively the minimum. Append it to min_stack.
   • If self.min_stack is NOT empty, compare val to the current minimum (which is sitting at self.min_stack[-1]). Append whichever is smaller to self.min_stack.
3. pop: Pop from BOTH self.stack and self.min_stack.
4. top: Return self.stack[-1].
5. getMin: Return self.min_stack[-1].

class MinStack:
    def __init__(self):
        self.stack = []
        self.min_stack = []

    def push(self, val: int) -> None:
        self.stack.append(val)
        
        # If min_stack has items, push the smaller of the new val or the current min
        if self.min_stack:
            current_min = self.min_stack[-1]
            self.min_stack.append(min(val, current_min))
        else:
            self.min_stack.append(val)

    def pop(self) -> None:
        self.stack.pop()
        self.min_stack.pop()

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

    def getMin(self) -> int:
        # The current minimum is always sitting right at the top of the min_stack
        return self.min_stack[-1]

Time & Space Complexity

• Time complexity: O(1) for all operations (push, pop, top, and getMin). Appending to and popping from the end of a list are constant time operations.
• Space complexity: O(N) where N is the number of elements in the stack. We are effectively storing twice as many elements as the brute force method, but it still scales linearly.