Min Stack

Thought Process

The Min Stack problem requires designing a stack that supports push, pop, top, and retrieving the minimum element in constant time. Here are two approaches:

Approach 1: Two Stacks - Use two stacks i.e. 'st' for regular stack operations and 'minStack' to track minimum values. When pushing, compare the new value with the current minimum and push the smaller value to 'minStack'. Both stacks are always kept in sync, ensuring getMin() always returns the top of minStack.

Approach 2: Linked List -Use a linked list where each node stores its value and the minVal up to that point. The head node always contains both the top value and current minimum. Each push operation updates the minVal by comparing with the previous minimum.

Approach 1: Two Stacks

class MinStack {

    Stack<Integer> st;
    Stack<Integer> minStack;

    public MinStack() {
        st = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int val) {
        
        if(st.isEmpty()){
            st.push(val);
            minStack.push(val);
        }
        else{
            st.push(val);
            minStack.push(Math.min(val,getMin()));
        }
    }
    
    public void pop() {
        st.pop();
        minStack.pop();
    }
    
    public int top() {
        return st.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Approach 2: Linked List

class Node{

    int val;
    int minVal;
    Node next;

    Node(int val){
        this.val = val;
        this.minVal = val;
        next = null;
    }
}
class MinStack {

    Node head;
    public MinStack() {
        head = null;
    }
    
    // 'head' node always stores the current minimum & the top element 
    // of the stack.
    public void push(int val) {
        
        Node nod = new Node(val);
        
        if(head==null){
            nod.minVal = val;
            head = nod;
        }
        else{
            nod.minVal = Math.min(getMin(),val);
            nod.next = head;
            head = nod;
        }
    }
    
    public void pop() {
        head = head.next;
    }
    
    public int top() {
        return head.val;
    }
    
    public int getMin() {
        return head.minVal;
    }
}

/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(val);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Code Complexity

Time Complexity: O(1) for all operations

Both approaches provide constant time operations for push, pop, top, and getMin.

Space Complexity: O(n)

Both approaches use linear space to store the stack elements and their minimum values.