-1

Objective Find minimum value in stack in O(1) time complexity.

Issue : Failing at the below operation (2*x-minEle) in some Leetcode testcases.

Actual Error - runtime error: signed integer overflow: 2 * -2147483648 cannot be represented in type 'int'

I tried replacing every integer value with long long datatype but still getting the same error

Following is the code:

class MinStack {
public:
    int minEle = INT_MAX;
    vector<int> s;
    void push(int x) {
        if(s.empty())
        {
            minEle=x;
            s.push_back(x);
            return;
        }
        if(x<minEle)
        {
            s.push_back(2*x-minEle);
            minEle = x;
        }
        else
            s.push_back(x);    
    }
    
    void pop() {
        int y = s.back();
        if(y<minEle)
        {
            minEle = 2*minEle - y;
        }
        s.pop_back();
    }
    
    int top() {
        return s.back();
    }
    
    int getMin() {
        return minEle;
    }
};
Asesh
  • 2,871
  • 1
  • 19
  • 30
AP7
  • 25
  • 1
  • 7
  • 2
    What do you hope to learn from these contest/challenge/competitive coding/hacking sites? If it's to learn C++, you won't learn anything there. Like in this case, the correct solution is based on a mathematical or a programming trick. If you don't know what the trick is and attempt to code a brute-force approach, the program either runs slow, or fails to handle an obscure edge case. If you're trying to learn C++, you won't learn anything from meaningless online contest sites [but only from a good C++ textbook](https://stackoverflow.com/questions/388242/the-definitive-c-book-guide-and-list). – Sam Varshavchik Dec 03 '20 at 03:40
  • 1
    I disagree. Programming challenges can be fun, help you think about how algorithms work, and keep you motivated to make progress. Many people do not learn best from books, but through experience (ideally paired with a book for a theoretical grounding). – Tumbleweed53 Dec 03 '20 at 04:58
  • 1
    The opinions about competitive programming sites aside ..... in this case, the flaw in question can be easily triggered with `int main() {MinStack x; x.push(0); x.push(INT_MIN);}`. Work out how to adjust the code to work correctly in this case, and you will address that problem. I offer no assurances that is the *only* flaw in the code though. – Peter Dec 03 '20 at 08:59

1 Answers1

0

I also face the same problem on a programming challenge site but didn't encounter an "integer overflow" on IDE. "long long" data type works for me on IDE.

Bhupesh Kumar
  • 1
  • 1