Why did OJ think my resulting array is empty? (C solution)


  • 0
    G

    My code below gave correct answer on my machine but OJ said:

    Submission Result: Wrong Answer

    Input: [1], 1

    Output: []

    Expected: [1]

    The result array seemed not filled successfully. But I did fill it.

    Can anybody tell what is wrong in my code?

    int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
        int resSize = numsSize - k + 1;
        returnSize = &resSize; 
        
        int * res = (int*) malloc( sizeof(int) * (*returnSize) );
        int * dq = malloc( numsSize * sizeof(int) ); // a deque to store the potential maximum elements
        int start = 0;
        int end = -1;
      
        if( numsSize==0 ){
            return res;
        }
    
        int i = 0; // consider the first k
        while( i < k ){
            while( end >= start && nums[ dq[end] ] <= nums[i] ){
                end--; // delete the elements that cannot be the maximum
            }
            end++;
            dq[end] = i; // push i
            i++;
        }
      
        i = k;
        int resEnd = -1;
        while( i < numsSize ){
            resEnd++;
            res[resEnd] = nums[ dq[ start ] ]; // maximum element is always the first element of the deque
            
            while( end >= start && nums[ dq[end] ] <= nums[i] ){
                end--;
            }
            end++;
            dq[end] = i;
    
            while( end >= start && dq[start] <= i-k ){
                start++; // delete the elements out of the window
            }
    
            i++;
        } 
      
        resEnd++;
        res[resEnd] = nums[ dq[start] ];
        
        return res;    
    }
    

    Thank you in advance!


  • 0

    Instead of:

    returnSize = &resSize; 
    

    You should do this:

    *returnSize = resSize;
    

    The reason is returnSize = &resSize assigns the address of resSize to the variable returnSize, which is a copy of returnSize's address. Therefore, it has no effect on the value where returnSize points to when the function is done.

    Another way to think about is when you pass int x to a function, for example: void foo(int x), doing x = 3 inside the function does not affect the variable on the caller's side, because the variable was passed in as a copy to the function.


  • 0
    G

    Great. It works. But I can't understand why the code worked on my own machine. Could it be the case the memory in my machine keep some value for returnSize?

    By the way, there is another separate bug in my code, i.e., if( numsSize==0 ){ return res;} should be replaced with if( numSize==0){return NULL;} and put in the begin of the function.


  • 0
    G

    1337c0d3r, resSize is allocated in the call stack of function maxSlidingWindow. So when the function returns, the call stack is released (although other may or may not use the same memory immediately). If the place resSize is allocated is then reused by other code, then the data there might be modified, thus returnSize will get a different value or more likely a runtime error/segmentation fault. If that piece of memory is not modified by chance, then it would be what guohua saw (getting correct result).


Log in to reply
 

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