An intuitive constant-space solution in C, well-commented and accepted as best


  • 2
    int* productExceptSelf(int* nums, int size, int* returnSize)
    {
        int* arr = (int*)malloc(sizeof(int)*size); //the result array;
        arr[0] = 1;
        for(int i = 1; i < size; i++) //collect the product of left side;
            arr[i] = arr[i-1] * nums[i-1];
        int t = nums[size-1]; //using t to collect the right side;
        for(int i = size-2; i > -1; i--) //merge t and arr, we get the product except self;
        {
            arr[i] *= t;
            t *= nums[i];
        }
        *returnSize = size;
        return arr;
    }

  • 0
    K

    Very technical and easy to understand !


  • 0
    T

    Although time O(2n) == O(n), I am confused by many questions that if a problem should be done in time O(n), it is meant to be one pass, or two passes are OK. Just for the sake of discussion, if I do in three passes, will O(3n) is still considered as O(n)?


  • 0

    In theory all O(kn) is equal to O(n), but when it comes to the specific space cost when it is easy to be retrieved, we can dig deeper for details and as a result we will get so-called O(2n) or O(3n) as you mentioned.


  • 0
    T

    I actually means time O(n), not space, as your space usage is alright. Sometimes I was misled to think in one pass if required to do in time O(n), but maybe time O(2n) or even time O(3n) are all OK.


  • 0

    The analysis mentioned above can be applied in both space and time complexity, man. Maybe you should check some reference about the big O and then you will get some hold of it. Good luck.


Log in to reply
 

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