# O(n) time and O(1) space C++ solution with explanation

• First, consider O(n) time and O(n) space solution.

``````class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
vector<int> fromBegin(n);
fromBegin[0]=1;
vector<int> fromLast(n);
fromLast[0]=1;

for(int i=1;i<n;i++){
fromBegin[i]=fromBegin[i-1]*nums[i-1];
fromLast[i]=fromLast[i-1]*nums[n-i];
}

vector<int> res(n);
for(int i=0;i<n;i++){
res[i]=fromBegin[i]*fromLast[n-1-i];
}
return res;
}
};
``````

We just need to change the two vectors to two integers and note that we should do multiplying operations for two related elements of the results vector in each loop.

``````class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n=nums.size();
int fromBegin=1;
int fromLast=1;
vector<int> res(n,1);

for(int i=0;i<n;i++){
res[i]*=fromBegin;
fromBegin*=nums[i];
res[n-1-i]*=fromLast;
fromLast*=nums[n-1-i];
}
return res;
}
};``````

• OK, if doesn't count the space of the return array, it is O(1) space.

• It's easy to understand, but really hard for me to come up on my own! Amazing!

• Java version:

``````class Solution {
public int[] productExceptSelf(int[] nums) {
int[] res = new int[nums.length];
Arrays.fill(res, 1);
int fromBegin = 1;
int fromEnd = 1;
for (int i = 0; i < nums.length; ++i) {
res[i] *= fromBegin;
fromBegin *= nums[i];
res[nums.length - 1 - i] *= fromEnd;
fromEnd *= nums[nums.length - 1 - i];
}
return res;
}
}
``````

• @ltong2016 是我菜，没理解～_～

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