pop() function for stack referred by min not working properly?

Question

I was attempting a question on leetcode and not sure about this anomalous behaviour. I am providing the logic part of the question. Please let me know if any discrepancy is found.

Question: Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.

push(x) -- Push element x onto stack.

pop() -- Removes the element on top of the stack.

top() -- Get the top element.

getMin() -- Retrieve the minimum element in the stack.

Link to leetcode question

Approach: Using 2 stacks, values (with original values in their order) and min (with values sorted in ascending order)

    class MinStack {

        Stack<Integer> min;
        Stack<Integer> values;

        /** initialize your data structure here. */
        public MinStack() {
            min = new Stack<>();
            values = new Stack<>();
        }

        public void push(int x) {
            if(values.isEmpty()){
                values.push(x);
                min.push(x);
            }
            else{
                values.push(x);
                if(min.peek()<x){
                    List<Integer> list = new ArrayList<>();
                    while(!min.isEmpty() && min.peek()<x)
                        list.add(min.pop());
                    min.push(x);
                    for(int i=list.size()-1;i>=0;i--)
                        min.push(list.get(i));
                }
                else
                    min.push(x);
            }
            System.out.println("min after push-->"+min);
            System.out.println("values after push -->"+values);

        }

        public void pop() {

                if(values.peek()==min.peek()){
                    min.pop();
                }

                else{
                   List<Integer> list = new ArrayList<>();
                    while(!min.isEmpty() && min.peek()!=values.peek()){
                         list.add(min.pop());
                    }
                       if(!min.isEmpty()){
                             min.pop();
                       }


                    for(int i=list.size()-1;i>=0;i--)
                        min.push(list.get(i));
                }
           values.pop();

            System.out.println("min after pop -->"+min);
            System.out.println("values after pop-->"+values);

        }

        public int top() {
            System.out.println("min on top -->"+min);
            System.out.println("values on top-->"+values);
           return values.peek();
        }

        public int getMin() {
            System.out.println("min for getMin-->"+min);
            System.out.println("values for get min-->"+values);
            return min.peek();
        }
    }

    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */

your `push` and `pop` are not constant-time operations since they contain loops — mangusta, Jun 05 '20 at 01:34
@mangusta Agreed. Thanks. Still pop is not working on min. Like it has no effect. it just stays as is. Any specific reason for that? — Arnav Bhattacharya, Jun 05 '20 at 01:49
@mangusta - ["MinStack","push","push","push","push","pop","getMin","pop","getMin","pop","getMin"] [[],[512],[-1024],[-1024],[512],[],[],[],[],[],[]] — Arnav Bhattacharya, Jun 05 '20 at 03:24
could you also specify the pushed values? (for `push` operations) — mangusta, Jun 05 '20 at 03:25
@mangusta - Already specified. Sequence being - [[],[512],[-1024],[-1024],[512],[],[],[],[],[],[]] — Arnav Bhattacharya, Jun 05 '20 at 04:28
I mean, specify which value was pushed for every push operation, otherwise it's unclear which element was pushed at which moment — mangusta, Jun 05 '20 at 04:42
You may want to read about the [Heap data structure](https://en.m.wikipedia.org/wiki/Heap_(data_structure)). — Bohemian, Jun 08 '20 at 01:58

muasif80 · Accepted Answer · 2020-06-09T09:32:17.740

1

The wrapper classes like Integer, Long should use equals rather than ==

Use equals here if(values.peek()==min.peek()){

Change it to if(values.peek().equals(min.peek())){
Also min.peek()!=values.peek() to !min.peek().equals(values.peek())
The last thing is you remove the System.out.println lines
One more suggestion would be to not use entire stack for sorted values and recreate it everytime a pop is done on the actual stack.

Rather you should maintain a single min variable and update it if the pop has removed the min item. You can find minimum value using min() method from stream()

You can have a look at the following too

Java: Integer equals vs. ==

How to properly compare two Integers in Java?

edited Jun 09 '20 at 09:32

answered Jun 08 '20 at 01:38

muasif80

5,586
4
32
45

@ArnavBhattacharya Did this answer help you? – muasif80 Jun 08 '20 at 05:36
OK. Please accept the answer and upvote as it worked successfully. Thanks. – muasif80 Jun 09 '20 at 09:30
@ArnavBhattacharya What kind of obstacle possibly prevented you from accepting the answer? – Cortex Jun 09 '20 at 09:43
@Cortex - Didn't get you – Arnav Bhattacharya Jun 09 '20 at 18:55
I was wondering, since you saw the answer and found it useful .. why didn't you accept it but you eventually did J – Cortex Jun 09 '20 at 22:04

pop() function for stack referred by min not working properly?

1 Answers1