My C++ solution, O(n) time with no extra space

  • 17
    vector<int> productExceptSelf(vector<int>& nums) {
        int N = nums.size();
        vector<int> res(N,1);
        for(int i=0; i<N; i++){
            if (i==0)   res[i] = 1;
            else res[i] = res[i-1]*nums[i-1];
        int r_prod = 1;
        for(int i=N-1; i>=0; i--){
            res[i] *= r_prod;
            r_prod *= nums[i];
        return res;

  • 0

    SO COOL!!
    The most important thing which I forgot is that "2n" equals "O(n)"

  • 2

    why O(n) space?the problems said the return array doesn't take into account!

  • 0

    "no extra space"? I see N, i and r_prod.

  • 0

    So cool ! your code is readable but could you please give more explanation about how to think of this brliant solution?

  • 1

    Two passes. During the 1st pass (from left to right), res[i] records nums[0]xnums[1]x...xnums[i-1], the products of all elements till nums[i]. During the second pass (from right to left), res[i] is multiplied by nums[i+1]xnums[i+2]x...xnums[N-1], the products of all elements from i+1 till the end.

  • 0
    This post is deleted!

  • 0

    Same Concept but single for:

        vector<int> result (nums.size(), 1);
        int left = 1, right = 1;
        for (int i = 1; i < nums.size(); i++){
            left *= nums[i - 1];
            result[i] *= left;
            right *= nums[nums.size() - i];
            result[nums.size() - i - 1] *= right;
        return result;

  • 1

    @ManuelP by "no extra space" he means O(1). In other words, constant amount of space. Constant means, that the amount of extra space isn't a function of how many elements are given to the method.

  • 0

    so cool.
    in first loop, replaced with for(int i = 1; i < N; i++), no need for if(i==0) res[i] = 1 else.

Log in to reply

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