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.

Use an additional stack which keeps track of
the mins.

1      public class StackWithMin2 extends Stack<Integer> {
2               Stack<Integer> s2;
3               public StackWithMin2() {
4                      s2 = new Stack<Integer>();       
5           }
6           public void push(int value){
7                  if (value <= min()) {
8                         s2.push(value);
9                  }
10                 super.push(value);
11          }
12          public Integer pop() {
13                 int value = super.pop();
14                 if (value == min()) {
15                        s2.pop();           
16                 }
17                 return value;
18          }
19          public int min() {
20                 if (s2.isEmpty()) {
21                        return Integer.MAX_VALUE;
22                 } else {
23                        return s2.peek();
24                 }
25          }
26     }