Min Stack

Problem

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.

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

Constraints:

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

Solution

Approach: Two Stacks

The key insight is to maintain two stacks: one for all values and one for tracking the minimum at each level. Each element in the min stack represents the minimum value from the bottom up to that position.

When we push a value:

Always push to the main stack
Push to the min stack only if it’s less than or equal to the current minimum

When we pop:

Always pop from the main stack
Pop from the min stack only if the popped value equals the current minimum

Implementation

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

    def push(self, val: int) -> None:
        self.stack.append(val)
        # Push to min_stack if it's the new minimum
        if not self.min_stack or val <= self.min_stack[-1]:
            self.min_stack.append(val)

    def pop(self) -> None:
        if self.stack:
            val = self.stack.pop()
            # If we're popping the minimum, update min_stack
            if self.min_stack and val == self.min_stack[-1]:
                self.min_stack.pop()

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

    def getMin(self) -> int:
        return self.min_stack[-1] if self.min_stack else None

Alternative (Storing Tuples):

class MinStack:
    def __init__(self):
        self.stack = []  # Each element is (value, current_min)

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append((val, val))
        else:
            current_min = min(val, self.stack[-1][1])
            self.stack.append((val, current_min))

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

    def top(self) -> int:
        return self.stack[-1][0] if self.stack else None

    def getMin(self) -> int:
        return self.stack[-1][1] if self.stack else None

Complexity Analysis

Time Complexity: O(1) for all operations (push, pop, top, getMin).
Space Complexity: O(n), where n is the number of elements. In the worst case (strictly decreasing sequence), both stacks will have n elements.

Key Insights

Two Stack Approach: By maintaining a parallel min stack, we can track the minimum at any point in O(1) time. The min stack always has the minimum value for the corresponding main stack state.
Synchronization: We only push to the min stack when we find a new minimum (or equal value). This keeps the min stack smaller in many cases while maintaining the correct minimum.
Tuple Approach: Storing (value, current_min) tuples in a single stack is cleaner but uses slightly more space since every element stores the minimum.
Edge Case - Duplicates: When the minimum value appears multiple times, we must track all occurrences. That’s why we push to min_stack when val <= min_stack[-1] (not just <).