C solution (dynamic programming) in O(n) and O(1) space*


  • 0
    E

    We are given the hint that this problem can be solved in O(1) space, excluding the size of the output array. That just SCREAMS "dynamic programming". Dynamic programming may not help you with your job, but it will help you get a job. But I digress...

    We solve the problem in a two-pass approach, taking advantage of our output array as scratch space. Specifically, our two passes are as follows:

    Pass 1: Walk the input array "forwards", and set each element of the output array to equal the product of the input array, from from element 0 and up to but not including the current element. Since there are no elements "before" element 0, we set element 0 of the output to 1, and set each subsequent output element to the product of the previous input element and the previous output element.

    Pass 2: Walk the array "backwards" and keep a temporary variable ("accumulator") containing the product of all the elements we've seen so far, excluding the current element. For each element we see, we multiply our current accumulator value by the corresponding element of our output array. Since each element of the output array already contains the product of the input array from 0 and up to the current element, we "complete" the product by multiplying each element by the accumulator, which contains the product of all elements from the current element up to the end of the array.

    int* productExceptSelf(int* nums, int len, int* returnSize) {
        int *ret, i, tmp = 1;
    
        *returnSize = len;
        ret = malloc(*returnSize * sizeof(int));
        
        ret[0] = 1;
    
        for (i = 1; i < len; i++)
            ret[i] = ret[i - 1] * nums[i - 1];
    
        for (i = len - 1; i >= 0; i--) {
            ret[i] *= tmp;
            tmp *= nums[i];
        }
        
        return ret;
    }
    

Log in to reply
 

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