Min Stack

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 value) pushes the element value 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:

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

Approach: Dual Stack (Optimal Solution)

Algorithm

1. Use a main stack to store all values
2. Use a second stack to track the running minimum
3. On push(value): push to the main stack, and push to the min stack the smaller of value and the current minimum
4. On pop(): pop from both stacks
5. On top(): peek the main stack
6. On getMin(): peek the min stack

Key Insight

The min stack stores the minimum value at each stack level. Because both stacks grow and shrink together, the top of the min stack always reflects the minimum of the current main stack. This makes getMin() an O(1) peek.

Time & Space Complexity

• Time Complexity: O(1) for every operation
• Space Complexity: O(n) - both stacks store up to n elements

Java Implementation

import java.util.Stack;

public class MinStack {

    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    /** Initialize the stack object. */
    public MinStack() {
        stack = new Stack<>();
        minStack = new Stack<>();
    }

    /** Push value onto the stack. */
    public void push(int value) {
        stack.push(value);
        // Track the minimum: if minStack is empty, current value is the min
        if (minStack.isEmpty() || value <= minStack.peek()) {
            minStack.push(value);
        }
    }

    /** Remove the top element. */
    public void pop() {
        if (stack.isEmpty()) {
            return;
        }
        int top = stack.pop();
        // If the popped value was the current min, pop it from minStack too
        if (top == minStack.peek()) {
            minStack.pop();
        }
    }

    /** Get the top element. */
    public int top() {
        return stack.peek();
    }

    /** Retrieve the minimum element in the stack. */
    public int getMin() {
        return minStack.peek();
    }

    // Test method
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);
        System.out.println("getMin(): " + minStack.getMin()); // Expected: -3
        minStack.pop();
        System.out.println("top(): " + minStack.top());       // Expected: 0
        System.out.println("getMin(): " + minStack.getMin()); // Expected: -2
    }
}

Example Walkthrough

For the sequence push(-2), push(0), push(-3), getMin(), pop(), top(), getMin():

1. push(-2): stack=[-2], minStack=[-2]
2. push(0): stack=[-2,0], minStack=[-2] (0 > -2, not pushed)
3. push(-3): stack=[-2,0,-3], minStack=[-2,-3] (-3 <= -2, pushed)
4. getMin(): peek minStack → -3
5. pop(): pop -3 from stack. -3 == minStack.peek() → pop -3 from minStack. stack=[-2,0], minStack=[-2]
6. top(): peek stack → 0
7. getMin(): peek minStack → -2

Alternative Approach: Single Stack with Pairs

import java.util.Stack;

class MinStackPairs {
    private Stack<int[]> stack;

    public MinStackPairs() {
        stack = new Stack<>();
    }

    public void push(int value) {
        int min = stack.isEmpty() ? value : Math.min(value, stack.peek()[1]);
        stack.push(new int[]{value, min});
    }

    public void pop() {
        stack.pop();
    }

    public int top() {
        return stack.peek()[0];
    }

    public int getMin() {
        return stack.peek()[1];
    }
}

This variant stores a (value, minSoFar) pair per stack level, using a single stack instead of two.

Key Insights

1. Constant Time: Every operation, including getMin(), runs in O(1)
2. Synchronized Stacks: The min stack only pushes when a new minimum appears, keeping memory efficient
3. Pop Consistency: The min stack is popped exactly when its top matches the popped value
4. Edge Cases: Handles duplicate minimums correctly because <= allows multiple identical min entries

The dual-stack approach satisfies all O(1) requirements for the Min Stack problem.