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

• ``````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;
}``````

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

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

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

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

• 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.

• This post is deleted!

• 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;``````

• @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.

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

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