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

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;
}
}
}

• I must be missing something here... if you have a data structure that can push, pop, and return min in $O(1)$, can't you use it to sort $n$ numbers in $O(n)$, which should be impossible? You simply push them all in and then pop out the minimum $n$ consecutive times. – Federico Poloni Feb 21 '16 at 15:58
• @FedericoPoloni: You are indeed missing something => you cannot pop the minimum. You can pop the top element, but it is not necessarily the minimum, indeed if you push 2, 1, 3 (in this order) the resulting stack is (top to bottom): (3, 1), (1, 1), (2, 2). – Matthieu M. Feb 21 '16 at 17:12
• @MatthieuM. It makes sense now - thanks for the explanation. – Federico Poloni Feb 21 '16 at 18:15

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()) {
} 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;
}
}
}

• I see two things with this: 1. consider ArrayDeque instead of LinkedList, as it performs better for the current use case (LinkedList is best if you frequently insert and remove in the middle of the collection) 2. peek() usually returns null, if the collection is empty, but this throws NoSuchElementException. – Thraidh Feb 21 '16 at 19:40

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.

• Note that in the worst case (elements pushed in descending order), the second stack is likely to take quite more space than a single stack with duplicated elements. It's worth taking into account the fact that a bare int is quite small (4 bytes) so doesn't add much overhead... actually, in 64 bits mode, it might very well be folded into padding bits. – Matthieu M. Feb 21 '16 at 19:09
• How do you handle the case of multiple occurrences of the minimum value with a secondary stack and you pop one of the minimum values? – holroy Feb 21 '16 at 19:30
• @holroy That's a good point. For push operations, you need to push to the min-stack if the element is less than or equal to the top of the min-stack. So after his examples if you Push(1) the min-stack becomes 3 1 1. – Carl Leth Feb 22 '16 at 0:10