Stack having push, pop and return min in O(1)

Question

I am using a class which is taking care of minimum value so far. Please let me know of any improvements or suggestions.

class MinStack {

    Stack<Node> s1 = new Stack<>();

    public void push(int x) {
        if(s1.isEmpty()) {
            s1.push(new Node(x,x));
        } else {
            s1.push(new Node(x,Math.min(s1.peek().min, x)));
        }

    }

    public void pop() {
        s1.pop();
    }

    public int top() {
        return s1.peek().val;
    }

    public int getMin() {
        return s1.peek().min;
    }

    static class Node{
        int val;
        int min;
        public Node(int v, int m) {
            val = v;
            min = m;
        }
    }
}

Answer 1

The general algorithm is great. At first, I thought you were overwriting the value with the min value, though, and it's because the fact that the Node stores two values is not very visible. A comment would help a lot here, and separating the logic in to a few lines too. This line:

s1.push(new Node(x,Math.min(s1.peek().min, x)));

should be:

int previousMin = backingStack.peek().minSoFar;
int minSoFar = Math.min(previousMin, value);
backingStack.push(new Node(value, minSoFar));

Note that I have also renamed all your variables. x is a poor name for a value. An x is a coordinate. s1 is another poor name, because where is s0, s2, etc... and what does s mean? min is not horrible, but it gives no indication of what it is the minimum of... what the context is.

Then, why are you using a Stack as the back-end implementation? I know it seems logical to use java.util.Stack, but you should know that it is not a recommended class any more. Stacks should be implemented over something that implements the Deque interface like java.util.LinkedList. The existing Stack class is bad because it is based on top of Vector which is a synchronized class that has a few implementation issues that are not recommended. The Stack class has this to say: "A more complete and consistent set of LIFO stack operations is provided by the Deque interface and its implementations, which should be used in preference to this class.". The Vector class has this to say: "Unlike the new collection implementations, Vector is synchronized. If a thread-safe implementation is not needed, it is recommended to use ArrayList in place of Vector."

So, Stack is bad. I would use:

private final Deque<Node> stack = new LinkedList<>();

Now, about the pop() method. It is a very C-like thing to split the pop() and "get" methods. Java, and most other languages, return the top value with the pop() call and avoid the need for a second call. Your pop() should return a value. You also need an isEmpty() Method so that people know when they have run out of data before they get a NoSuchElementException.

Oh, and the Node class can be private.

So, something like:

public class MinStack {

    private final Deque<Node> stack = new LinkedList<>();

    public void push(int value) {
        if(stack.isEmpty()) {
            stack.addFirst(new Node(value, value));
        } else {
            int minSoFar = Math.min(value, stack.getFirst().stackMin);
            stack.push(new Node(value, minSoFar));
        }
    }

    public boolean isEmpty() {
        return stack.isEmpty();
    }

    public int pop() {
        return stack.removeFirst().value;
    }

    public int peek() {
        return stack.getFirst().value;
    }

    public int getMin() {
        return stack.getFirst().stackMin;
    }

    private static class Node{
        int value;
        int stackMin;
        public Node(int val, int min) {
            value = val;
            stackMin = min;
        }
    }
}

Answer 2

Since @rolfl already targetted the majority of code related issues, I want to mention another technicality, which might be less important but good to know/mention.

This typical interview-questions has multiple solutions. The main 2 directions are:

1. Keeping the minimum in each node (like you did).
2. Using a second stack which is in charge of remembering the minimums.

Now since your solution looks clean (keep in mind the comments made by @rolfl). Why would one opt for the second solution and decide to maintain a second stack?

Consider the scenario where you have an incredibly large Stack. By keeping the minimum stored in each Node itself, you waste a lot of space.

Instead using a second stack which only keeps track of the minimums and updates the stack accordingly:

• For push operations, check if the pushed element is the new minimum. If this is the case, push it on the second stack.
• For pop operations, check if the popped element has the same value as the current minimum. If this is the case pop from the second stack too.

The advantage of this is: If your minimum is located at the first pushed element on your stack. The second stack will only contain that single value. In your scenario each node will hold this value.

An example:

Push(3):
stack: 3
min-stack: 3

Push(1):
stack: 3 1
min-stack: 3 1

Push(2):
stack: 3 1 2
min-stack: 3 1

Push(7):
stack: 3 1 2 7
min-stack: 3 1

Push(8):
stack: 3 1 2 7 8
min-stack: 3 1 

You can notice that for this small example of 5 nodes, only 2 have to be stored on the min-stack.