## Stack with function min in O(1) time

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

My initial thoughts:
We can keep an record of the current minimum element and dynamically update it when doing the push. However, the update cannot be kept when poping. Therefore I can only implement a O(1) push(), min() but O(n) pop() data structure.

My initial codes:

```public class Q3_2 {

private StackNode<Integer> top = null;
private Integer min = Integer.MAX_VALUE;

public void push(Integer item) {
StackNode<Integer> t = new StackNode<Integer>(item);
t.setUnderneath(top);
top = t;

if (item < min)
min = item;
}

public Integer pop() {
if (top == null)
return null;
Integer data = top.getData();
top = top.getUnderneath();

if (data == min) {
min = Integer.MAX_VALUE;
StackNode<Integer> curr = top;
while (curr != null) {
if (curr.getData() < min)
min = curr.getData();
curr = curr.getUnderneath();
}
}

return data;
}

public Integer min() {
return min;
}
}

Solution:
public class StackWithMinNode<T> extends StackNode<T> {

private Integer min = null;
private StackWithMinNode<T> underneath = null;

public StackWithMinNode(T item) {
super(item);
}

public Integer min() {
return min;
}

public void setMin(Integer min) {
this.min = min;
}

@Override
public StackWithMinNode<T> getUnderneath() {
return underneath;
}

public void setUnderneath(StackWithMinNode<T> underneath) {
this.underneath = underneath;
}

}

public class StackWithMin extends MyStack<Integer> {

StackWithMinNode<Integer> top = null;

@Override
public void push(Integer data) {
StackWithMinNode<Integer> item =
new StackWithMinNode<Integer>(data);
if (top != null)
item.setMin(Math.min(data, top.min()));
else
item.setMin(data);
item.setUnderneath(top);
top = item;
}

@Override
public Integer pop() {
if (top == null)
return null;
Integer data = top.getData();
top = top.getUnderneath();
return data;
}

public Integer min() {
if (top == null)
return null;
}
}

The idea is similar as my initial thought, only that we keep a local minimum for each node.
Another solution is implemented using an auxiliary stack to keep track of the local minimum, therefore potentially saving spaces taken by keep track local min for each single node.
public class StackWithMinStack extends MyStack<Integer> {

MyStack<Integer> minStack = new MyStack<Integer>();

@Override
public void push(Integer data) {
StackNode<Integer> item = new StackNode<Integer>(data);
if (minStack.isEmpty())
minStack.push(data);
else {
if (data.compareTo(minStack.peek()) <= 0)
minStack.push(data);
}
item.setUnderneath(top);
top = item;
}

@Override
public Integer pop() {
if (top == null)
return null;
Integer data = top.getData();
if (data.compareTo(minStack.peek()) == 0)
minStack.pop();
top = top.getUnderneath();
return data;
}

public Integer min() {
if (minStack.isEmpty())
return null;
return minStack.peek();
}
}

Comment: Be careful about line 11. We push into the auxiliary stack if we have found element less OR equal to the local min. We have to keep duplicates in order to further deal with the case where one duplicate is poped. Think about this stack from top to bottom (on the right is its auxiliary stack, storing the local min):
5
2
4 2
2 2
7 7
If we only store one 2 in the auxiliary stack, then when 5 and 2 are poped from the original stack, the auxiliary stack will only be left with 7, resulting in a wrong global min.

__ATA.cmd.push(function() {
__ATA.initVideoSlot('atatags-370373-5c9102b9960cf', {
sectionId: '370373',
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-26942-5c9102b996119',  {
collapseEmpty: 'before',
sectionId: '26942',
width: 300,
height: 250
});
});

__ATA.cmd.push(function() {
__ATA.initSlot('atatags-114160-5c9102b99611b',  {
collapseEmpty: 'before',
sectionId: '114160',
width: 300,
height: 250
});
});