Min Stack

Problem Link

155. Min Stack – LeetCode

Problem Statement

Design a stack that supports the following operations in constant time:

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

• int getMin() – Retrieves the minimum element in the stack.

Examples

Example 1:

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

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

Constraints

• -2³¹ <= val <= 2³¹ - 1

• At most 3 * 10⁴ calls will be made to push, pop, top, and getMin

• pop, top, and getMin will always be called on non-empty stacks

Intuition

To support getMin() in O(1) time, we need a way to track the minimum element at each point in the stack’s history.

The idea is to maintain a second stack (minStack) that always holds the minimum element so far corresponding to the top element of the main stack.

Approach: Two Stacks (Main + Min Stack)

1. Maintain two stacks:

   • stack: Stores all pushed values.

   • minStack: Stores the minimum element at each level of the stack.

2. On push(val):

   • Push val to stack.

   • Push min(val, minStack.peek()) to minStack.

3. On pop():

   • Pop both stack and minStack.

4. On top():

   • Return stack.peek().

5. On getMin():

   • Return minStack.peek().

Java Code

class MinStack {
    private Stack<Integer> stack;
    private Stack<Integer> minStack;

    public MinStack() {
        this.stack = new Stack<>();
        this.minStack = new Stack<>();
    }

    public void push(int val) {
        stack.push(val);
        int min = Math.min(val, minStack.isEmpty() ? val : minStack.peek());
        minStack.push(min);
    }

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

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

    public int getMin() {
        return minStack.peek();
    }
}

Time and Space Complexity

Dry Run

Input:

push(-2), push(0), push(-3), getMin(), pop(), top(), getMin()

Stack States:

Conclusion

This is a classic stack design problem that uses an auxiliary min-tracking stack to achieve constant time operations for retrieving the minimum element.

It’s a useful pattern for designing custom data structures with enhanced operations.