My code works on my machine but gives a wrong answer on leetcode


  • 0
    S

    My code is as follows:

    class MinStack {
        stack<long> myStack;
        long min;
    public:
        void push(int x) {
            if (myStack.empty()){
                myStack.push(0);
                min = x;
            }
            else{
                myStack.push(x-min);
                if (x < min) min = x;
            }
            
        }
        void pop() {
            if (!myStack.empty()) {
                long x = myStack.top();
                if (x < 0) min = min-x;
                myStack.pop();
            }
        }
        int top() {
            long x = myStack.top();
                if (x > 0) return (int)(x + min);
                else return (int)min;
    
        }
        int getMin() {
            return (int)min;
        }
    };
    

    The test case I failed was the one involving long numbers:

    Input:	push(2147483646),push(2147483646),push(2147483647),top,pop,getMin,pop,getMin,pop,push(2147483647),top,getMin,push(-2147483648),top,getMin,pop,getMin
    Output:	[2147483647,2147483646,2147483646,2147483647,2147483647,-2147483647,-2147483648,-2147483648]
    Expected:	[2147483647,2147483646,2147483646,2147483647,2147483647,-2147483648,-2147483648,2147483647]
    

    However, on my XCode, my code gives exactly what is expected. Anyone please advise?


  • 0
    S

    The error is not happening before 4th push. Let's then look at the behavior of the code starting from 4th push and afterwards.

    Stack is empty at this point
    
    push (2147483647): this will produce:
    0 will be pushed into the stack as stack was empty
    stack has onlly one element 0
    min equals 2147483647
    
    top(): this will produce:
    stack stays unchanged and will have only one element 0
    returns 2147483647
    
    getMin(): this will produce:
    returns 2147483647
    
    push(-2147483648): this will produce:
    "x - min" = -2147483648 - 2147483647
    This will overflow and the result will become 1
    so now 1 will be pushed into the stack
    x (-2147483648) is less than min (2147483647)
    so min becomes -2147483648
    
    top(): this will produce:
    x = stack top = 1
    x (1) is greater than 0 so return (x + min)
    x (1) + min (-2147483648) = -2147483647
    so it returns **-2147483647** instead of returning *-2147483648*
    

  • 0
    S

    Checking back again. Did my explanation made any sense? Were you able to fix your code based on it?


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.