ctci/03. Stacks and queues/3.2. min_function.md

3.2. Stack Min

Design a stack which has a function min, returning the minimum element. Push, pop and min should all operate in O(1) time.

First idea

If it's supposed to be O(1) like pop, then just get another variable min in the class. But min must be updated every time a pop or push happens! I could have another function update to update the min but that's basically an appendix to pop and push so it doesn't work. If the new item to be pushed is lower than min, just update it. But what about pop? Then I'd have to do O(n). Either we do O(n) in time, or O(n) in space and have a stack of ordered values.

public class MyStack<T> {
    private static class StackNode<T> {
        // attributes of nodes in the stack
        private T data;
        private StackNode<T> next;

        public StackNode(T data){
            this.data = data;
        }
    }

    // attribute of the stack
    private StackNode<T> top;
    private StackNode<T> min;
    min.data = 999;

    public T pop() {
        if (top == null){
            throw new EmptyStackException();
        }
        T item = top.data;
        top = top.next;
        return item;
    }

    public void push(T item) {
        StackNode<T> t = new StackNode<T>(item);
        if (item < min) {
            min = item;
        }
        t.next = top;
        top = t;
    }
}

Hints

1. The min element doesn't change very often. Only changes when a smaller elem is added or the smallest elem is popped
2. What about storing extra data at each node? what sort of data might it be?
   1. The next bigger element? That's O(n) space like before.
3. Consider having each node know the minimum of its "substack" (all the elements beneath it, including itself).

public class MyStack<T> {
    private static class StackNode<T> {
        // attributes of nodes in the stack
        private T data;
        private StackNode<T> next;
        private T min;

        public StackNode(T data){
            this.data = data;
        }
    }

    // attribute of the stack
    private StackNode<T> top;

    public T pop() {
        if (top == null){
            throw new EmptyStackException();
        }
        T item = top.data;
        top = top.next;
        return item;
    }

    public void push(T item) {
        StackNode<T> t = new StackNode<T>(item);
        // first addition to stack or smaller numbers
        if (top == null || item < top.min) {
            t.min = item;
        }
        t.next = top;
        top = t;
    }

    public void get_min() {
        if (top == null){
            throw new EmptyStackException();
        }
        return top.min;
    }
}

Solution

Having just an integer works well except when the minimum element is popped, then it takes O(n) to update the stack. But for larger stacks, it takes a lot of space. We could create a stack of mins. Code for solution.