How to Find the Max Integer Value in a Stack without using max() or iterating over it?

Question

I was asked in an interview the following question: if you have a Stack of Integers how would you find the max value of the Stack without using Collections.max and without iterating over the Stack and comparing elements. I answered it with the below code as I don't know of another way than using any Collections API or iterating over the Stack and using comparisons. Any ideas?

import java.util.Collections;
import java.util.Stack;

public class StackDemo {
    public static void main(String[] args){
        Stack lifo = new Stack();
        lifo.push(new Integer(4));
        lifo.push(new Integer(1));
        lifo.push(new Integer(150));
        lifo.push(new Integer(40));
        lifo.push(new Integer(0));
        lifo.push(new Integer(60));
        lifo.push(new Integer(47));
        lifo.push(new Integer(104));

        if(!lifo.isEmpty()){
            Object max = Collections.max(lifo);
            System.out.println("max=" + max.toString());
        }
    }
}

Answer 1

By using Collections.min() instead:

if (!lifo.isEmpty()) {
  Integer max = Collections.min(lifo, new Comparator<Integer>() {
    @Override
    public int compare(Integer o1, Integer o2) {
      return o2.compareTo(o1);
    }
  });
  System.out.println("max=" + max.toString());
}

Note that the custom Comparator flips the comparison so that Collections.min() will actually return the max.

Answer 2

import java.util.Collections;
import java.util.Stack;

public class StackDemo {
    public static void main(String[] args) {
        Stack lifo = new Stack();
        lifo.push(new Integer(4));
        lifo.push(new Integer(1));
        lifo.push(new Integer(150));
        lifo.push(new Integer(40));
        lifo.push(new Integer(0));
        lifo.push(new Integer(60));
        lifo.push(new Integer(47));
        lifo.push(new Integer(104));

        System.out.println("max= 150"); // http://xkcd.com/221/
    }
} 

Answer 3

Edit:

without iterating over the Stack

does not actually prohibit all iteration. Rather, the question only prohibits doing the simple

for (Integer i : lifo)

Thus, this solution satisfies the question's limitations.

---

Just empty a copy of the stack. pop each of the elements from the copy, checking for max against an integer all the while.

Stack<Integer> lifoCopy = (Stack<Integer>) lifo.clone();
int max = Integer.MIN_VALUE;

while (!lifoCopy.isEmpty())
{
    max = Math.max(lifoCopy.pop(), max);
}

System.out.println("max=" + max.toString());

This will work for you in O(n) time even if your interviewers decide to be more restrictive and not allow more built in functions (max, min, sort, etc.).

Additionally, if you need to have the original unharmed, but can't use clone, you can do so with an extra stack:

Stack<Integer> reverseLifo = new Stack<Integer>();
int max = Integer.MIN_VALUE;

while (!lifo.isEmpty())
{
    int val = lifo.pop();

    max = Math.max(val, max);

    reverseLifo.push(val);
}

while (!reverseLifo.isEmpty())
{
    lifo.push(reverseLifo.pop());
}

System.out.println("max=" + max.toString());

Finally, this assumes that comparison against a temp variable is acceptable. If no comparison is allowed at all, then this solution in conjunction with this method will work.