Question

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 0(1) time.

Solution

This is a very tricky question.

The key is how to use the minimum space to achieve O(1) query min operation. The trick is to count how many times the same min-value occur. Eg.

input: 5,3,3,1,1,2,2,2,2,2,2,2.

stack: 5,3,3,1,1.

So we can pop ‘1’ twice, pop ‘3’ twice, and pop ‘5’ once. Read the code!

Code

public class StackMyAnswer extends Stack<Integer> {

    Stack<Integer> min = new Stack<Integer>();

    public void push(int value) {
        if (min.isEmpty() || value <= min.peek()) {
            min.push(value);
        }
        super.push(value);
    }

    public Integer pop() {
        int val = super.pop();
        if (!min.isEmpty() && val == min.peek()) {
            min.pop();
        }
        return val;
    }

    public int min() {
        if (min.isEmpty()) {
            return Integer.MAX_VALUE;
        }
        return min.peek();
    }
}