Solution by rohitnandi12


  • 2
    R

    Primary Thoughts

    Stack is a LIFO (Last in First Out) abstract data type with operations such as push and pop and is a linear data structure.

    The Questions demands to get the minimum at any particular instance, it means there will be one or more operations carried on the stack and the updated minimum element has to be returned when the getMin function is called.

    Questions To The Interviewer

    Many situations are not mentioned in question. Possible questions you can ask to the interviewer are.

    • Output when pop is performed on a empty stack
    • Output when top is performed on a empty stack
    • Output when getMin is performed on a empty stack

    In this questions it has been assumed that there wont be any situation when the operations are been made on the empty stack. (This i can to know after experimenting with different test cases)

    Approach #1 [ Time Limit Exceeded ]

    Intuition

    Use a stack to hold the new elements. When getMin is called traverse the stack and return the minimum element at that instance.

    Java Solution

    class MinStack {
    
        /** initialize your data structure here. */
        Stack<Integer> buff = null;
        public MinStack() {
            buff = new Stack<>();
        }
    
        public void push(int x) {
            buff.push(x);
        }
    
        public void pop() {
            buff.pop();
        }
    
        public int top() {
            return buff.peek();
        }
    
        public int getMin() {
            Stack<Integer> temp = new Stack<>();
            int currentMin = Integer.MAX_VALUE;
    
            while(!buff.isEmpty()){
                if(currentMin>buff.peek())
                    currentMin = buff.peek();
                temp.push(buff.pop());
            }
            while(!temp.isEmpty()){
                buff.push(temp.pop());
            }
            return currentMin;
        }
    }
    
    

    Complexity Analysis

    Time complexity :

    push : $$O(1)$$.
    pop : $$O(1)$$.
    top : $$O(1)$$.
    getMin : $$O(n)$$. Though getMin has Big-O of O(n), but you can see from code that elements are traversed twice when getMin is called.

    Space complexity : $$O(n))$$.


    Approach #2 Using Auxiliary Stack [Accepted]

    Intuition

    A auxiliary stack, say minSt, can be used which is going to store the minimum at any instance when an element is pushed. At any instance the top element of minSt is going to hold the most updated minimum element. Trick is to on call of pop check if the pop element is the minimum element then pop and element from minSt too.

    Java

    class MinStack {
        /** initialize your data structure here. */
        Stack<Integer> st = null;
        Stack<Integer> minSt = null;
        public MinStack() {
            st = new Stack<>();
            minSt = new Stack<>();
        }
    
        public void push(int x) {
            st.push(x);
            if(minSt.isEmpty()){
                minSt.push(x);
            }else if(x<=minSt.peek()){
                minSt.push(x);
            }
        }
    
        public void pop() {
            if(st.peek().equals(minSt.peek())){
                minSt.pop();
            }
            st.pop();
        }
    
        public int top() {
            return st.peek();
        }
    
        public int getMin() {
            return minSt.peek();
        }
    }
    
    

    Complexity Analysis

    • Time complexity : $$O(1)$$

    • Space complexity : $$O(2n)$$ for the minSt and buff


    Approach #3 Without Auxilliary Stack [Accepted]

    ** Intuition**

    We can avoid minSt and store the minimum element in buff itself.

    ** Algorithm **

    constructor

    • initialize variable currentMin
    • initialize stack buff

    push

    • push the old minimum value when the current minimum value changes after pushing the new value x
    • push the new value

    pop

    • if pop operation could result in the changing of the current minimum value,
      pop twice and change the current minimum value to the last minimum value.

    top

    • return top value of buff

    getMin

    • return currentMin

    Java

    class MinStack {
        int currentMin = Integer.MAX_VALUE;
        Stack<Integer> buff = new Stack<Integer>();
    
        public void push(int x) {
            if(x <= currentMin){
                buff.push(currentMin);
                currentMin=x;
            }
            buff.push(x);
        }
    
        public void pop() {
            if(currentMin == buff.pop()) currentMin=buff.pop();
        }
    
        public int top() {
            return buff.peek();
        }
    
        public int getMin() {
            return currentMin;
        }
    }
    
    

    Complexity Analysis

    • Time complexity : $$O(1)$$

    • Space complexity : $$O(n)$$ for the buff

    Thank You for your up-vote. Happy Coding :-)


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.