How from O(N) to O(1)


  • 24

    Here is the O(N) based C++ implementation

    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int len=nums.size();
            vector<int> left(len, 1);
            vector<int> right(len, 1);
            vector<int> result(len, 0);
            for(int i=1; i<len; i++)  left[i]=left[i-1]*nums[i-1];
            for(int i=len-2; i>=0; i--)  right[i]=right[i+1]*nums[i+1];
            for(int i=0; i<len; i++) result[i]=left[i]*right[i];
            return result;
        }
    };
    

    How to use O(1) ?

    By observing the above code, we can just for every position multiply it to its right position.

    Just the idea to think reversly !

    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int n=nums.size();
            int left=1, right=1;
            vector<int> result(n, 1);
            for(int i=0; i<n; i++){
                result[i]*=left;
                result[n-1-i]*=right;
                left*=nums[i];
                right*=nums[n-1-i];
            }
            return result;
        }
    };

  • -2
    S
        int* productExceptSelf(int* nums, int numsSize, int* returnSize)
        {
            int* output;
            int i, j;
            int sum;
            
            output = (int*)malloc(sizeof(int)*numsSize);
            *returnSize = numsSize;
            sum = 1;
            for( i = 0; i < numsSize; ++i )
                if( nums[i] != 0 )
                    sum *= nums[i];
            for( i = 0; i < numsSize; ++i )
                if( nums[i] != 0 )
                    output[i] = sum / nums[i];
                else
                {
                    memset( output, 0, sizeof(int)*numsSize );
                    output[i] = sum;
                    for( j = 0; j < numsSize; ++j )
                        if( j != i && nums[j] == 0 )
                        {
                            output[i] = 0;
                            break;
                        }
                    break;
                }    
            return output;
        }

  • 0

    Please use in the right format !!!


  • 0
    G

    usually, use ++i batter than i++


  • 0
    Z

    How is this O(1)? You are still going through all of the items once, so I believe the second solution is O(n) as well. In the first solution you are iterating through 3 times, so it is O(3*n) which equals to O(n).


  • 0
    N

    Its O(1) with respect to space complexity (as asked in the follow-up part of the question to do in constant space), and not time complexity which you think he is referring to. It is not possible to do this in time complexity less than O(n) because every element has to be visited at least once.


  • 0
    Z

    Ah, I misunderstood then, I thought he meant O(1) time complexity. But yes, O(n) is the minimum, we are on the same page on that.


  • 0
    F

    in fact, this is just the combination of 2 loops to compute the left and right acculumated product. So we can combine the 2 loop into one loop as the below implementation.

    class Solution {
    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int n = nums.size();
            int left = 1, right = 1;
            vector<int> result(n, 1);
            for (int i = 0; i < n; i++) {
                result[i] *= left;
                left *= nums[i];
                //result[n-1-i] *= right;
                //right *= nums[n-1-i];
            }
            for (int i = 0; i < n; i++) {
                //result[i] *= left;
                //left *= nums[i];
                result[n-1-i] *= right;
                right *= nums[n-1-i];
            }
            return result;
        }
    };

  • 0
    T
    This post is deleted!

Log in to reply
 

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