Min Stack

How it works

This approach keeps only one stack and stores encoded values instead of the actual numbers. The trick is to record the difference between the pushed value and the current minimum. Whenever a new minimum is pushed, we store a negative encoded value, which signals that the minimum has changed. Later, when popping such a value, we can decode it to restore the previous minimum.

This way, the stack internally keeps track of all minimum updates without needing a second stack — giving constant-time operations with minimal space.

Steps

1. Maintain:
   • stack → stores encoded values (not the actual numbers)
   • min → stores the current minimum in the stack
2. Push(val):
   • If the stack is empty:
     • Push 0 (difference) and set min = val.
   • Otherwise:
     • Push val - min.
     • If val is the new minimum, update min.
3. Pop():
   • Pop the encoded value.
   • If this value is negative, it means the popped element was the minimum.
     • Restore the previous minimum using the encoded difference.
4. Top():
   • If the encoded value is positive, return encoded + min.
   • If it's negative, the top actual value is simply min.
5. getMin():
   • Return the current min.

Complexity

• Time complexity: O(1) for all operations.
• Space complexity: O(n)

Things to watch for

Not Synchronizing the Two Stacks

When using the two-stack approach, some implementations only push to minStack when the new value is smaller than the current minimum. This optimization requires careful handling during pop(): you must only pop from minStack when the popped value equals the current minimum. Forgetting this synchronization causes minStack to become misaligned with the main stack, returning incorrect minimums.

Integer Overflow in the Encoded Value Approach

The one-stack solution stores val - min as encoded values. When dealing with extreme integer values (e.g., Integer.MIN_VALUE and Integer.MAX_VALUE), this subtraction can overflow. Using long instead of int for the encoded values and the minimum prevents this issue in languages with fixed-width integers.

class MinStack:
    def __init__(self):
        self.min = float('inf')
        self.stack = []

    def push(self, val: int) -> None:
        if not self.stack:
            self.stack.append(0)
            self.min = val
        else:
            self.stack.append(val - self.min)
            if val < self.min:
                self.min = val

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

        pop = self.stack.pop()

        if pop < 0:
            self.min = self.min - pop

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

    def getMin(self) -> int:
        return self.min

class MinStack {
private:
    long min;
    std::stack<long> stack;

public:
    MinStack() {}

    void push(int val) {
        if (stack.empty()) {
            stack.push(0);
            min = val;
        } else {
            stack.push(val - min);
            if (val < min) min = val;
        }
    }

    void pop() {
        if (stack.empty()) return;

        long pop = stack.top();
        stack.pop();

        if (pop < 0) min = min - pop;
    }

    int top() {
        long top = stack.top();
        return (top > 0) ? (top + min) : (int)min;
    }

    int getMin() {
        return (int)min;
    }
};