# 238. Product of Array Except Self

Description:

https://leetcode.com/problems/product-of-array-except-self/#/description

Algorithm:

As shown in Code.

Code1 (62ms, beats 20.95%):

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> fromLeft = vector<int>(n, 1);
vector<int> fromRight = vector<int>(n, 1);
vector<int> result = vector<int>(n, 1);

for (int i = 1; i < nums.size();i++)
{
fromLeft[i] = nums[i – 1] * fromLeft[i – 1];
}
for (int i = nums.size() – 2; i >= 0;i–)
{
fromRight[i] = nums[i + 1] * fromRight[i + 1];
}

for (int i = 0; i < nums.size();i++)
{
result[i] = fromLeft[i] * fromRight[i];
}
return result;
}
};

Code2 (46ms, fastest):

class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {

vector<int> res;

res.push_back(1);

for(int i = 1; i<nums.size(); i++){

int temp = res[i-1]*nums[i-1];

res.push_back(temp);

}

int right = 1;

for(int i = nums.size()-1; i>=0; i–){

res[i] *= right;

right *= nums[i];

}

return res;

}
};