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

@StephenTG Nope, can't get arbitrary elements without popping the stack. — nanofarad, Jul 24 '13 at 18:04
You could use recursion that imitates iteration though. Hacky, but would technically avoid the no iteration restriction — StephenTG, Jul 24 '13 at 18:05
Crazy long shot, but how literally should we take "comparing elements"? Does comparing *an* element to an intermediate variable still count (i.e. iterate over the stack, keeping a local maximum and comparing each element to that maximum value) — lc., Jul 24 '13 at 18:08
Is this Question Java Specific, or interviewer wnated to aks you something different? — Grijesh Chauhan, Jul 24 '13 at 18:09
I can't see a way to do this if the stack is just handed to you and you're not allowed to look at the contents. Maybe the answer is "define a new Stack subclass where you override the `push` operation to update an internally-stored max value, and then define `public int max(){ return this.maxValue; }`"? — Henry Keiter, Jul 24 '13 at 18:09
I suggest that you first write, in English with pencil and paper, a description of the steps you need to solve the problem. — Code-Apprentice, Jul 24 '13 at 18:26
My solution uses only built in functions of stack and no iteration or recursion. — Luke Willis, Jul 24 '13 at 18:46
@LukeW. As long as my postulate holds that comparing a single element to a temporary variable does not constitute "comparing elements" — lc., Jul 24 '13 at 18:48
Can we use StackSort? http://xkcd.com/1185/ (mouseover image) — Luke Willis, Jul 24 '13 at 19:41
@HenryKeiter - I was thinking the same thing. Often times the idea of these questions if to see how you think/problem solve - taking a step back and asking a question like this demonstrates that — Christoph, Jul 24 '13 at 22:37
This question appears to be off-topic because it is not a constructive question and is generating mostly jokes and discussion. — Ben Jackson, Jul 25 '13 at 20:26
Possible duplicate of [Stack with find-min/find-max more efficient than O(n)?](https://stackoverflow.com/questions/7134129/stack-with-find-min-find-max-more-efficient-than-on) — Ed J, Oct 17 '19 at 18:01

DannyMo · Answer 1 · 2013-07-24T18:59:16.450

31

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.

edited Jul 24 '13 at 18:59

answered Jul 24 '13 at 18:09

DannyMo

11,344
4
31
37

1

Yes, interesting design consideration. – nanofarad Jul 24 '13 at 18:09
10

I'm not confident that this is in the spirit of the challenge, but I love the implementation :D – Henry Keiter Jul 24 '13 at 18:11
12

@HenryKeiter You're probably right, but I couldn't pass up the opportunity to be a smart-ass! – DannyMo Jul 24 '13 at 18:18
6

If it weren't kind of an obnoxious question, I'd say this was an obnoxious answer... but in context, it's perfect. – mjfgates Jul 24 '13 at 22:22

score 11 · Answer 2 · edited Oct 23 '14 at 19:48

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

score 10 · Accepted Answer · edited May 23 '17 at 10:30

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.

@BenJackson OP intended no `for (Integer i : lifo)`. This is not iterating over the stack so much as it is iterating until the stack is empty. — Luke Willis, Jul 25 '13 at 14:59

Smit · Answer 4 · 2013-07-24T18:38:48.167

10

Not sure will this satisfy your question need, but this way use of max() and iteration could be avoided, anyhow sort does use iteration and Comparable in background.

if (!lifo.isEmpty()) {
    Stack sc = (Stack) lifo.clone();
    Collections.sort(sc);
    System.out.println("max=" + sc.get(sc.size() - 1));
}

edited Jul 24 '13 at 18:38

answered Jul 24 '13 at 18:15

Smit

4,685
1
24
28

I'm guessing this is the answer – lc. Jul 24 '13 at 18:17
@lc. Not sure, but this way stack order can be preserved while satisfying the OPs need. – Smit Jul 24 '13 at 18:23
1

Sorry I was asked to not use the Collections.sort either – c12 Jul 24 '13 at 18:29
1

@Smit _Collections.sort()_ uses comparisons in the background as well. – Juvanis Jul 24 '13 at 18:33
2

@c12 your question should reflect this. – Luke Willis Jul 24 '13 at 18:33
1

@Juvanis Thanks for heads up. let me update the answer. and @ c12 I agree with @ LukeW. – Smit Jul 24 '13 at 18:38

score 7 · Answer 5 · edited May 23 '17 at 12:26

This code:

public static Integer max(Stack stack) {
    if (stack.isEmpty()) {
        return Integer.MIN_VALUE;
    }
    else {
        Integer last = (Integer)stack.pop();
        Integer next = max(stack);
        stack.push(last);
        if (last > next) {
            return last;
        }
        else {
            return next;
        }            
    }
}

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(Arrays.deepToString(lifo.toArray()));
    System.out.println(max(lifo));
    System.out.println(Arrays.deepToString(lifo.toArray()));
}

outputs:

[4, 1, 150, 40, 0, 60, 47, 104]
150
[4, 1, 150, 40, 0, 60, 47, 104]

It is a recursion on a given stack, finds the maximum element and doesn't change the stack order.

However iteration is different from recursion only if you define it like that. Also, to find maximum you must compare all the elements somehow - in whatever mathematical form, with relational or bitwise operators like Anirudh showed. IMHO, pretty vaguely defined task.

I concur on the vagueness of the question. Some terms need to be clearly defined in the context, for it to be solvable. — afsantos, Jul 24 '13 at 19:36

score 6 · Answer 6 · edited May 23 '17 at 12:18

6

You can use bitwise operator instead..

public int getMax(int a, int b) 
{
    int c = a - b;
    int k = (c >> 31) & 0x1;
    int max = a - k * c;
    return max;
}

Now you can do

int max=Integer.MIN_VALUE-1; 
while(!stack.empty())
{
    max=getMax(max,stack.pop());
}

edited May 23 '17 at 12:18

Community

1
1

answered Jul 24 '13 at 18:22

Anirudha

32,393
7
68
89

works, but destroys the stack. +1 for the `getMax` function. If the stack needs to be maintained, you need to `clone()` or maintain another stack as I discuss in my answer. – Luke Willis Jul 24 '13 at 18:52
@LukeW. you can evade two stacks with recursion. see my answer. I think that anirudh's comparison and my recursion forms the answer. Unless of course, by "maintaining the stack" you mean not to pop/push it's elements? – linski Jul 24 '13 at 18:57
@linski True, but the extra stack solution that I provide is not iterative regardless of how you define recursion. – Luke Willis Jul 24 '13 at 19:00
2

@LukeW. I disagree. From [wikipedia](http://en.wikipedia.org/wiki/Iteration#Computing), broader definition: "Iteration in computing is the repetition of a block of statements within a computer program." That cover's all the loops and recursion. That's why I think the task is vaguely defined. – linski Jul 24 '13 at 19:06

score 5 · Answer 7 · edited May 23 '17 at 10:30

5

This can be done in O(1) time and O(n) memory. Modify the push and pop method (or by inheritance extend the standard stack with your own) to keep track of the current max in another stack.

When you push elements onto your stack, push max(currentElem, maxStack.peek()) onto maxStack When you pop elements off the stack, pop the current max from your max stack as well.

This solution illustrates it well, so I won't expand more on it: https://stackoverflow.com/a/3435998/1007845

edited May 23 '17 at 10:30

Community

1
1

answered Jul 24 '13 at 18:24

Adrian

5,603
8
53
85

2

I think this must be the correct answer. Outlawing "iteration" sounds like code for O(1) way to get max, which can only be done with a special data structure, not a generic `java.util.Stack` – Ben Jackson Jul 25 '13 at 00:43

score 4 · Answer 8 · answered Jul 24 '13 at 18:52

4

Time to think outside of the box. Use the Wolfram Alpha REST API, and ask it to compute the result of:

"maximum of " + Arrays.deepToString(lifo.toArray())

It will return 150.

answered Jul 24 '13 at 18:52

lc.

113,939
20
158
187

score 2 · Answer 9 · answered Jan 16 '17 at 20:56

1 x -Push the element x into the stack.

2 -Delete the element present at the top of the stack.

3 -Print the maximum element in the stack.

    import java.io.*;
    import java.util.*;
    import java.text.*;
    import java.math.*;
    import java.util.regex.*;
    public class Solution {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            Stack <StackItem> st = new Stack <StackItem> ();
            int n = sc.nextInt();//number of choice
            int choice;
            int max = 0;
            for (int i = 0; i<n; i++) {
               choice = sc.nextInt();
               if (choice == 1) {//insert/push an item
                  int newInt = sc.nextInt();
                  if (!st.isEmpty()) {
                      max = st.peek().currentMax;
                  } else {
                      max = 0;
                  }
                  if (newInt > max) {
                        max = newInt;
                  }
                  StackItem item = new StackItem(newInt, max);
                  st.push(item);
                } else if (choice == 2) {//pop
                    if (!st.isEmpty()) st.pop();
                } else if (choice == 3) {//print the maximum item
                    System.out.println(st.peek().currentMax);
                }
            }
        }
    }
    class StackItem {
        int val;
        int currentMax;
        StackItem(int val, int max) {
            this.val = val;
            this.currentMax = max;
        }
    }

score 1 · Answer 10 · answered Jul 24 '13 at 18:06

1

When you push elements into the stack, update the max value

void main()
    int max = Integer.min
    lifo.push(1)

while

   void push(Integer value) {
       //push into stack
       //update max value
   }

answered Jul 24 '13 at 18:06

StevenTsooo

498
4
13

5

Can this be assumed? I believe you are only given a stack of integers. – Vivin Paliath Jul 24 '13 at 18:06

score 1 · Answer 11 · edited Jul 24 '13 at 18:31

1

You can convert it to a TreeSet with:

int myMax = new TreeSet<Integer>(lifo).last();

edited Jul 24 '13 at 18:31

arshajii

127,459
24
238
287

answered Jul 24 '13 at 18:07

nanofarad

40,330
4
86
117

Why are you declaring an explicit comparator here? – arshajii Jul 24 '13 at 18:11
@arshajii OK then. I'll edit it when I actually have a moment. Feel free to do the edits if you'd like. – nanofarad Jul 24 '13 at 18:28

score 1 · Answer 12 · answered Jul 24 '13 at 18:07

1

Use Collections.sort with a Comparator that sorts in descending order and then peek the top element from the Stack.

answered Jul 24 '13 at 18:07

jalynn2

6,397
2
16
15

1

I think OP wants to preserve the stack. – nanofarad Jul 24 '13 at 18:08
Perhaps the answer should at least allude to that. – nanofarad Jul 24 '13 at 18:09

score 1 · Answer 13 · edited Aug 10 '16 at 19:23

Here is my solution:

import java.util.Arrays;
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));

        Object lifoArray[] = lifo.toArray();
        Arrays.sort(lifoArray);
        System.out.println(lifoArray[lifoArray.length-1]);
    }
}

Arrays.sort() arranges in ascending order, so the last value in the sorted array will be the max value.

Ankit · Answer 14 · 2013-07-24T18:17:45.943

Without iteration you can do a recursive call. If it's not homework it isn't logical to do so. Or alternatively you can do this without iteration & recursion.

However a quick n simple approach is here:

public class StackDemo {
    public static int max = 0; //set this to least, may be negative
    public static Stack lifo = new Stack();
    public static void main(String[] args){        
        pushToStack(new Integer(4));
        pushToStack(new Integer(1));

        if(!lifo.isEmpty()){
            Object max = Collections.max(lifo);
            System.out.println("max=" + max);
        }
    }
    void static int pushToStack(Integer value){
        lifo.push(value);
        if(max<value){
        max = value;
        }
        return max;
    }    

}

no, its not. its just a non-iterative solution without using max(); — Ankit, Jul 24 '13 at 18:16

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

14 Answers14

Related