A clear c++ solution in O(n) time and O(1) space without division


  • 0
    W

    A clear c++ solution in O(n) time and O(1) space without division, but it's slow,hope some suggestions

    public:
        vector<int> productExceptSelf(vector<int>& nums) {
            int size = (int)nums.size();
            vector<int> output(size,1);
            /* calculate left product */
            int left_product = 1;
            for (int i=1;i<size;i++) {
                left_product *= nums[i-1];
                output[i] *= left_product;
            }
            /* calculate right product */
            int right_product = 1;
            for (int i=size-2;i>=0;i--) {
                right_product *= nums[i+1];
                output[i] *= right_product;
            }
            return output;
        }
    };

  • 0
    H

    Late but this code doesn't seem to be slow for me at all.
    If you were looking at ms, i think it's a poor way to look at the speed. Just need to know it's constant space complexity as well as O(N) time.

    I think this is a solid solution!


Log in to reply
 

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