Min Stack

Question: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

• push(x) — Push element x onto stack.
• pop() — Removes the element on top of the stack.
• top() — Get the top element.
• getMin() — Retrieve the minimum element in the stack.

Approach 1: The discussions section had quite a few brilliant ideas. Here’s one that seemed to inspire this solution. Let’s quickly check how this algorithm works on a simple example —

Pictorial representation of the algorithm for a simple example

And here’s the code —

//Approach 1:
//Runtime: 47ms
//Memory usage: 40.4MB
class MinStack {
    
    int min = Integer.MAX_VALUE;
    Node stack;
    
    class Node {
        int val;
        Node next;
        Node(int val){
            this.val = val;
            this.next = null;
        }
    }
/** initialize your data structure here. */
    public MinStack() {
        stack = null;
    }
    
    public void push(int x) {
        if(min>=x){
            //add copy of previous min
            add(min);
            min = x;
        }
        add(x);
    }
    
    private void add(int x){
        Node node = new Node(x);
        node.next = stack;
        stack = node;
    }
    
    public void pop() {
        if(stack!=null && stack.val==min){
            //an extra pop
            stack = stack.next;
            //now update  min
            if(stack!=null)
                min = stack.val;
        }
        if(stack!=null)
        stack = stack.next;
    }
    
    public int top() {
        return stack.val;
    }
    
    public int getMin() {
        return min;
    }
    
}
/**
 * Your MinStack object will be instantiated and called as such:
 * MinStack obj = new MinStack();
 * obj.push(x);
 * obj.pop();
 * int param_3 = obj.top();
 * int param_4 = obj.getMin();
 */

Cheers & Chao!