Min Stack (155)

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:

• Create a private inner class for the nodes in order to form the LinkedList.

• When pushing into the stack, add element to the head of LinkedList to simulate the LIFO property.

• To avert conducting a linear search when getMin() function is called, insert a min data field to Node class which will inform us of the min at each desired point consequently allowing retrieval in O(1).

• Since we always have a pointer to the head, when we pop, we simply move the pointer to the next Node.

class MinStack {
    
    Node head;

    /** initialize your data structure here. */
    public MinStack(){}
    
    public void push(int x) {
        if(head == null){
            head = new Node(x, x, null);
        }
        else{
            head = new Node(x, Math.min(x, head.min), head);
        }
    }
    
    public void pop() {
        head = head.next;
    }
    
    public int top() {
        return head.data;
    }
    
    public int getMin() {
        return head.min;
    }
    
    private class Node{
        int data;
        int min;
        Node next;
        
        public Node(int data, int min, Node next){
            this.data = data;
            this.min = min;
            this.next = next;
        }
    }
}

Time complexity: O(1) Space Complexity: O(N)