Min Stack

Question (LC.155)

Design a data structure that supports push(x), pop(), top(), and getMin() all in O(1) time.

Example

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); // return -3
minStack.pop();
minStack.top(); // return 0
minStack.getMin(); // return -2

Analysis

Besides the standard stack operations push(x), pop(), and peek(), we also need to support a heap operation getMin() in O(1) time. The first thought can be use a variable to keep track of the minimum value that works but when the min value gets popped out, we need to restore the second smallest value. This insight calls for a special type of stack - monotonic stack.

Monotonic Stack

A monotonic stack is a stack in which its elements are strictly increasing or decreasing. In this case, we want to use a decreasing stack to keep track of all the min values.

Illustration

We can use the example above.

push(-2) // stack.push(-2) if (decStack.isEmpty()) decStack.push(-2)
push(0) // stack.push(0) if (0 <= decStack.peek()) decStack.push(0)
push(-3) // stack.push(-3) if (-3 <= decStack.peek()) decStack.push(-3)

stack [-2, 0, -3]
decStack [-2, -3]

getMin() // return decStack.peek()
pop() // if (stack.pop() == decStack.peek()) decStack.pop()
top() // return stack.peek()
getMin() // return decStack.peek()

Implementation

class MinStack {    
    Stack<Integer> stack;
    Stack<Integer> decStack;

    public MinStack() {
        stack = new Stack<Integer>();
        decStack = new Stack<Integer>();
    }

    public void push(int x) {
        stack.push(x);
        if (decStack.isEmpty() || x <= decStack.peek()) {
            decStack.push(x);
        }
    }

    public void pop() {
        if (stack.pop().equals(decStack.peek())) {
            decStack.pop();
        }
    }

    public int top() {
         return stack.peek();
    }

    public int getMin() {
        return decStack.peek();
    }
}

Max Stack (LC.716)

Design a data structure that supports push(x), pop(), top(), peekMax() and popMax().

Analysis

In addition to function like a normal max stack, its an additional function popMax(). Let's implement the normal functionalities first, then look into popMax(). It turns we really just have to brute force this with two stacks. Using a temp stack to store the elements until we find max and pop it. The tricky part is that we have to push it back and update incStack.

Consider example

["MaxStack","push","push","popMax","peekMax"]
[[],[5],[1],[],[]]

stack [1]
incStack [!]

Code

class MaxStack {
    Stack<Integer> stack;
    Stack<Integer> incStack;    

    public MaxStack() {
        stack = new Stack<Integer>();
        incStack = new Stack<Integer>();        
    }

    public void push(int x) {
        stack.push(x);
        if (incStack.isEmpty() || x >= incStack.peek()) {
            incStack.push(x);
        }        
    }

    public int pop() {
        int pop = stack.pop();
        if (pop == incStack.peek()) {
            incStack.pop();
        }
        return pop;
    }

    public int top() {
        return stack.peek();
    }

    public int peekMax() {
        return incStack.peek();
    }

    public int popMax() {
        if (stack.isEmpty()) {
            return -1;
        }
        int max = incStack.pop();
        removeMax(max); // remove max from stack and update incStack
        return max;
    }

    // remove the max value from stack
    private void removeMax(int max) {
        // temp will store all the elements that are not max
        Stack<Integer> temp = new Stack<>();
        while (stack.peek() != max) {
            temp.push(stack.pop());
        }
        // found the max
        stack.pop();
        // push these elements back
        while (!temp.isEmpty()) {
            push(temp.pop().intValue());
        }
    }
}