Best C solution with O(n)


  • 0
    M

    When you use standard struct such as queue/hash/heap in C++ or Java, the built-in algorithms in C++/Java still has time/space complex.You can't ignore it.

    Following is my C resolution with a best complex (O(n)) compared to all resolutions I have seen in this problem.

    int* maxSlidingWindow(int* nums, int numsSize, int k, int* returnSize) {
    int i, j;
    int head, tail;

    int *ret;
    int *queue;
    
    if (nums == NULL || numsSize == 0) {
        *returnSize = 0;
        return NULL;
    }
    
    *returnSize = (numsSize - k + 1);
    ret = malloc(sizeof(int) * (*returnSize));
    
    /*An array to store all numbers might potentially be the maximum of the K size window, it works similarly with a queue */
    queue = malloc(sizeof(int) * numsSize);
    memset(queue, 0, sizeof(int) * numsSize);
    head = 0;
    tail = -1;
    j = 0;
    
    for (i = 0; i < numsSize; i ++) {
        /* Remove the items in the queue but smaller  than current item. This is O(n) as each item will only go into queue once 
         * and we will totally compare n times in maximum  
         */
        while (tail >= head && nums[i] > nums[queue[tail]]) {
            tail --;
        }
        queue[ ++ tail] = i;
        if (i - j + 1 == k) {
            ret[j ++] = nums[queue[head]];
        }
        while (head <= tail && i - queue[head] + 1 >= k) {
            head ++;
        }
    }
    
    free(queue);
    
    return ret;
    

    }


Log in to reply
 

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