#ctci

StackWithMin.java

// With a normal stack, to find the min at any time, we have to scan through all elements in the stack
// and this is taking O(n) time. How can we know the min of the stack at any time or at any state immediately?
// One way to do it is to save the min of the stack in any state somewhere.
//
// push, pop and min operation of the following data structre takes amortized O(1) time.
public class StackWithMin{
    private int N;
    private int capacity;
    private int[] data;
    private int[] mins;
    
    // Assume that the user will set a capacity > 0
    // otherwise we could throw an exception to warn the user
    public StackWithMin(int capacity) throws Exception{
        if(capacity <= 0) throw new Exception("the capacity must be positive!");
        this.capacity = capacity;
        N = 0;
        data = new int[capacity];
        mins = new int[capacity];
    }
    
    public void push(int val){
        if(N == capacity) resize(2*N);
        data[N] = val;
        if(N == 0) mins[N] = val;
        else mins[N] = mins[N-1] > val ? val : mins[N-1];
        N++;
    }
    
    public int pop() throws Exception{
        if(N == 0) throw new Exception("Stack underflow!");
        
        int tmp = data[--N];
        if(N == capacity / 4) resize(capacity / 2);
        return tmp;
    }
    
    public int min() throws Exception{
        if(N == 0) throw new Exception("Stack is empty!");
        return mins[N-1];
    }
    
    private void resize(int size){
        data = copyData(data, size);
        mins = copyData(mins, size);
        capacity = size;
    }
    
    private int[] copyData(int[] data, int size){
        int[] newData = new int[size];
        for(int i = 0; i < N; i++){
            newData[i] = data[i];
        }
        return newData;
    }
}