Runtime Error -- No idea what is wrong. Anyone could lend a hand?


  • 0
    G
    int maximumGap(vector<int> &num) {
        if (num.size() < 2) {
            return 0;
        }
        int min_val = num[0];
        int max_val = num[0];
        int n = num.size();
        for (int i=0;i<n;i++) {
            if (num[i] < min_val) {
                min_val = num[i];
            }
            if (num[i] > max_val) {
                max_val = num[i];
            }
        }
        
        int gap = ceil((double)(max_val - min_val)/(n - 1));
        int *mins = new int[n-1]();
        for (int i=0;i<n-1;i++) {
            mins[i] = -1;
        }
        int *maxs = new int[n-1]();
        for (int i=0;i<n-1;i++) {
            maxs[i] = -1;
        }
        
        for (int i=0;i<n;i++) {
            int index = (num[i] - min_val)/gap;
            if (mins[index] == -1 || mins[index] > num[i]) {
                mins[index] = num[i];
            }
            if (maxs[index] == -1 || maxs[index] < num[i]) {
                maxs[index] = num[i];
            }
        }
        
        int max_gap = -1;
        int prev_max = maxs[0];
        for (int i=1;i<n-1;i++) {
            if (mins[i] == -1) {
                continue;
            }
            
            if (mins[i] - prev_max > max_gap) {
                max_gap = mins[i] - prev_max;
            }
            
            prev_max = maxs[i];
        }
        
        return max_gap;
    }

  • 0
    M

    Variable gap can be zero, if max_val and min_val are the same, then later you divide on zero. Nobody garantee us, that elements do not repeat in the input array. Maybe this is the cause of runtime error.


  • 0
    G

    I tried adding

    if (gap == 0) {
    return 0;
    }

    And this didn't work either. Somewhere must be wrong, but the error message doesn't help that much


  • 0
    M
    int index = (num[i] - min_val)/gap;
    

    This index will be n-1 when num[i] points to max_val. So, mins[index] will be out of range in this case.


  • 0
    G

    marian -- you are right. thanks for your help

    I hope leetcode could provide the test case that really cause the problem, in stead of the previous successfully executed one.


  • 0
    M

    But actualy, in case of wrong answer, it shows you test case that breaks your program :)


  • 0
    G

    For wrong answer, that is true.
    But for runtime error, I don't think that's the case. And I saw many users complained about it.


  • 0
    M

    Yeah, for runtime error - no input values


Log in to reply
 

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