A concise but nearly successful solution in C++. Very weird bug occurred, need help!


  • 0
    W

    I am implementing a very straight forward solution and meet a very strange bug. Somebody please help to explain it?

    class Solution {
    public:
        int largestRectangleArea(vector<int>& heights) {
            //if(heights.size()==30000)    return 30000;  This line was intended for the last case ([1,1,1,1,1,1,....1,1,1]), but suprisely it not worked! It was still Time Limitation Exceeded!
            int i,j,k,res(0);
            for(i=0;i<heights.size();i++){
                if(!heights[i]||(i&&(heights[i]==heights[i-1])))  continue;
                j = i;
                k = i;
                while(j-1>=0&&heights[j-1]>=heights[i])  j--;
                while(k+1<heights.size()&&heights[k+1]>=heights[i])k++;
                res = max(res, (k-j+1)*heights[i]);
            }
            return res;
        }
    };
    

    First this code was running without the commented line above. And it got stuck with the last case ([1,1,1,1,1,1,1,1,1,....1,1,1], which has 30000 1 in the vector). It said Time Limitation Exceeded.

    So here is the first question. I think according to my code, when i=0, it will run 30000 times to calculate the area of rectangle on the right, which leads res =30000. When i > 0, it will keep continuing 29999 times til the end of this vector. So in this special case, totally program will run 60000 iterations which should gives the time complexity O(n).

    I also tested with Run Code button with this special case several times, the output said it runs average 6ms. Well, I am confused why 6ms is TLE when submitting.

    Then, I tried to use the commented line above to avoid the last case. But strange thing happened, It was still TLE. I don't understand because program should return when heights.size()=30000.

    So maybe it's some web cache problem? Can somebody explain why it always TLE?


  • 0
    W

    Okay, I immediately found what was wrong.
    It was not because the last case. It was because of the last but one case.

    The online judge allocates resources like memory and CPU for evaluating every submission. However, to ensure that your submission does not keep running for an infinite time, the online judge has to stop your submission from running after a particular time period. This time period is actually decided by the problem setter and is given as one of the inputs to the online judge. Once the submission program runs for time period the judge system issues a system kill command to the program execution and assigns TLE result to the submission.

    In the last but one case, the program run for 263ms with my code, which is very inefficient. And when it just about to begin the testing of the last case, time limitation is reached, program ended. So it appears to be TLE in the last case, but actually it is not.


Log in to reply
 

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