Min Stack

72.Min Stack

Stack

Design

Problem Statement:

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.

Example:

Input:

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

→

Output:

[-3, null, 0, -2]

Perform operations in sequence while keeping track of the minimum value.

Algorithm:

1. Use two stacks: one for normal stack operations, and one to track the current minimum.
2. For push: Add the element to the main stack and push the minimum of the new element or the current minimum to the min stack.
3. For pop: Remove the top element from both stacks.
4. For top: Return the top of the main stack.
5. For getMin: Return the top of the min stack.

class MinStack {
    
    Stack<Integer> s;
    Stack<Integer> min;

    // Initialize the stack and min stack
    public MinStack() {
        s = new Stack();
        min = new Stack(); 
    }
    
    // Push the value and update the min stack
    public void push(int x) {
        s.push(x);
        if (min.empty() || x < min.peek())
            min.push(x);
        else 
            min.push(min.peek());
    }
    
    // Pop from both stacks
    public void pop() {
        s.pop();
        min.pop();
    }
    
    // Return the top of the stack
    public int top() {
        return s.peek();
    }
    
    // Return the minimum value
    public int getMin() {
        return min.peek();
    }
}

Complexity:

Time: O(1) for all operations | Space: O(n)