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[i1]*nums[i1];
}
int r_prod = 1;
for(int i=N1; i>=0; i){
res[i] *= r_prod;
r_prod *= nums[i];
}
return res;
}
My C++ solution, O(n) time with no extra space

Two passes. During the 1st pass (from left to right), res[i] records nums[0]xnums[1]x...xnums[i1], 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[N1], the products of all elements from i+1 till the end.

@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 withfor(int i = 1; i < N; i++)
, no need forif(i==0) res[i] = 1 else
.