# Three different solutions (C++)

• ``````/* Stupid O(N^2) algorithm, Time Limit Exceed
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> res;

for (int i = 0; i < nums.size(); ++i) {
long product = 1;
for (int j = 0; j < nums.size(); ++j) {
if ( j != i)
product *= nums[j];
}

res.push_back(product);
}

return res;
}
};

*/
``````
``````/* Good O(N) time and O(N) space algorithm
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> res;
int n = nums.size();
vector<int> forwardProduct(n);
vector<int> backwardProduct(n);
forwardProduct[0] = 1;
backwardProduct[0] = 1;

for(int i = 1; i < nums.size(); ++i) {
forwardProduct[i] = forwardProduct[i - 1] * nums[i - 1];
backwardProduct[i] = backwardProduct[i - 1] * nums[n - i];
}

for (int j = 0; j < nums.size(); ++j)
res.push_back(forwardProduct[j] * backwardProduct[n - j - 1]);

return res;
}
};*/
``````
``````/* Very smart algorithm:  O(N) time and O(1) space */
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n = nums.size();
vector<int> res(n, 1);
int forwardProduct = 1;
int backwardProduct = 1;

for(int i = 0; i < n; ++i) {
res[i] *= forwardProduct;
forwardProduct = forwardProduct * nums[i];
res[n - i - 1] *= backwardProduct;
backwardProduct = backwardProduct * nums[n - i -1];
}

return res;
}
};
``````

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