Problem Statement

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

1. push(x) – Push element x onto stack.
2. pop() – Removes the element on top of the stack.
3. top() – Get the top element.
4. getMin() – Retrieve the minimum element in the stack.

Example:

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

Constraints:

• pop, top, and getMin will always be called on non-empty stacks.
• All operations should be O(1).

Approach

We need to keep track of the minimum value at all times. There are multiple ways to do this:

Method 1: Using Two Stacks

• Main stack stores all elements.
• Min stack stores the minimum element at each stage.
• When pushing, compare with the top of the min stack and push the smaller value to min stack.
• When popping, pop both stacks. The top of the min stack always has the current minimum.

Java Implementation

import java.util.Stack;

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

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

    public void push(int val) {
        stack.push(val);

        // If minStack is empty or val is smaller than current min, push it
        if (minStack.isEmpty() || val <= minStack.peek()) {
            minStack.push(val);
        } else {
            // Otherwise, push the current min again
            minStack.push(minStack.peek());
        }
    }

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

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

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

Usage Example

public class Main {
    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(-2);
        minStack.push(0);
        minStack.push(-3);

        System.out.println(minStack.getMin()); // -3
        minStack.pop();
        System.out.println(minStack.top());    // 0
        System.out.println(minStack.getMin()); // -2
    }
}

Explanation

1. Push Operation:
   • Push the element to the main stack.
   • Push the smaller of the new element and current minimum onto min stack.
2. Pop Operation:
   • Pop from both stacks. This ensures min stack is always aligned with main stack.
3. Top Operation:
   • Return the top element of the main stack.
4. getMin Operation:
   • Return the top element of the min stack, which is the current minimum.

Time Complexity:

• All operations (push, pop, top, getMin) are O(1).

Space Complexity:

• O(n) for storing elements in the two stacks.