Friday, December 26, 2014

Implement a stack whose push, pop and min operations all operate in O(1) time.

Q. How would you design a stack which, in addition to push and pop, also has a function min which returns the minimum element? Push, pop and min should all operate in O(1) time.

Algorithm:

1. Each stack element stores the value of that element and an index of the element that will be the lowest if the current element was removed.
2. int mI (field in class Stack) stores the index of the smallest element in the stack.
3. When we add an element we set it's lowest index value field to mI. If current element is smaller than lowest, mI is set to current index.
4. When we remove an element, if it is the mI index, we set mI to the local mI stored in that element.

Source:

import java.lang.reflect.Array;

public class Stack<T extends Comparable<T>>{
    class Element{
        T value;
        int nMI;
        Element(T v, int mI){
            value = v;
            nMI = mI;
        }
    }
    
    int top = -1, mI = 0;
    Element[] elements;
    Stack(int size){
        elements = (Element[])Array.newInstance(Element.class, size);
    }
    
    public void push(T value){
        if(top+1 == elements.length)return;
        Element el = new Element(value, mI);
        elements[++top] = el;
        if(top>0){
            if(elements[top].value.compareTo(elements[mI].value)<=0)
                mI = top; 
        } 
    }
    
    public T pop(){
        if(top == -1)return null;
        Element el = elements[top];
        if(mI == top)mI = elements[top].nMI;
        top--;
        if(top==-1)mI = -1;
        return el.value;
    }
    
    public T min(){
        if(mI == -1)return null;
        return elements[mI].value;
    }
    
    public boolean isEmpty(){
        return top==-1;
    }
    
    /*
    //For testing
    @Override
    public String toString(){
        String s = "";
        for(int i=0;i<=top;++i){
            s+=elements[i].nMI+" ";
        }
        return s;
    }
    */
}

public class Code{
    public static void main(String[] args){
        Integer[] input = {11,3,7,4,1,3,-1,2}; 
        Stack<Integer> s = new Stack<>(input.length+4);
        for(int i:input)s.push(i); 
        //System.out.println(s);
         
        System.out.println("Popping "+s.pop());
        System.out.println("Min = "+s.min()+"\n\n");
        s.pop();  
        s.push(44);
        s.push(-4);
        s.push(23);
        s.push(33);
        //System.out.println(s);
        while(!s.isEmpty()){
            System.out.println("Min: "+s.min());
            System.out.println("Popping: "+s.pop());
        } 
    }
}

Output:

Popping 2
Min = -1


Min: -4
Popping: 33
Min: -4
Popping: 23
Min: -4
Popping: -4
Min: 1
Popping: 44
Min: 1
Popping: 3
Min: 1
Popping: 1
Min: 3
Popping: 4
Min: 3
Popping: 7
Min: 3
Popping: 3
Min: 11
Popping: 11


Approach #2:

Using a separate field to record the min in each element requires more space. If the bottom element in the stack is the min, other upper elements are all saving it's index.

To fix this, we can instead use a separate stack that records the min. Whenever a new element is inserted, it checks if this is lesser than the min element we already have, if it is lesser or equal to the min value, we push it to the second stack.

If it is greater, we do nothing. When we pop() elements, we check if the element being popped is equal to the second stack's top element. If it is, we pop() the second stack too.


Source:


class Stack2<T extends Comparable<T>>{
    Stack<T> mS;
    
    int top = -1; 
    T[] elements;
    
    public Stack2(int size){ 
        elements = (T[])new Comparable[size]; 
        mS = new Stack<>(size);
    }
    
    public void push(T t){
        if(top+1 == elements.length){
            System.out.println("Overflow.");return;
        }
        elements[++top] = t;
        if(mS.isEmpty())mS.push(t);
        else{
            if(t.compareTo(mS.peek())<=0)
                mS.push(t);
        }
    }
    
    public T pop(){
        if(top<0){System.out.println("Underflow.");return null;}
        T val = elements[top--];
        if(val==mS.peek()) mS.pop(); 
        return val;
    }
    
    public T min(){
        if(!mS.isEmpty()) return mS.peek();
        return null;
    } 
    
    public boolean isEmpty(){
        return top==-1;
    }
    
    public static void main(String[] args){
        Integer[] input = {11,3,7,4,1,3,-1,2}; 
        Stack2<Integer> s = new Stack2<>(input.length+4);
        for(int i:input)s.push(i); 
        //System.out.println(s);
         
        System.out.println("Popping "+s.pop());
        System.out.println("Min = "+s.min()+"\n\n");
        s.pop();  
        s.push(44);
        s.push(-4);
        s.push(23);
        s.push(33);
        //System.out.println(s);
        while(!s.isEmpty()){
            System.out.println("Min: "+s.min());
            System.out.println("Popping: "+s.pop());
        } 
    }
}

public class Stack <T>{
    int top = -1; 
    T[] elements;
    
    public Stack(int size){
        elements = (T[])new Object[size]; 
    }
    
    public void push(T element){
        if(top+1 == elements.length){
            System.out.println("Overflow.");
            return;
        }
        elements[++top] = element;
    }
    
    public T pop(){
        if(top<0){
            System.out.println("Underflow.");
            return null;
        }
        return elements[top--];
    }
        
    public T peek(){
        if(top < 0){
            System.out.println("Stack is empty!");
            return null;
        }
        return elements[top];
    }
    
    public boolean isEmpty(){
        return top==-1;
    } 
}

Output:

Popping 2
Min = -1


Min: -4
Popping: 33
Min: -4
Popping: 23
Min: -4
Popping: -4
Min: 1
Popping: 44
Min: 1
Popping: 3
Min: 1
Popping: 1
Min: 3
Popping: 4
Min: 3
Popping: 7
Min: 3
Popping: 3
Min: 11

Popping: 11



elements = (T[])new Comparable[size]; 

When casting like this, take care to see 


elements = (T[])new Object[size]; 

will not work as you have declared <T extends Comparable<T>>

Object is being cast to some other object that must implement the Comparable Interface. But Object class itself doesn't implement this interface. This will cause classcastexception to be thrown. 

Use a Comparable[] array to fix this.

No comments:

Post a Comment