# [leetcode] Product of Array Except Self

Product of Array Except Self

Given an array of n integers where n > 1, `nums`, return an array `output` such that `output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

Solve it without division and in O(n).

For example, given `[1,2,3,4]`, return `[24,12,8,6]`.

Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

Dynamic programming.

dp[i] = nums[i] * nums[i+1] * … * nums.back()

```class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> ans;
vector<int> dp(nums.size(), 0);
dp[nums.size() - 1] = nums.back();
for(int i = nums.size() - 2; i >= 0; i--){
dp[i] = dp[i + 1] * nums[i];
}
int product = 1;
for(int i = 0; i < nums.size() - 1; i++){
ans.push_back(product * dp[i + 1]);
product = product * nums[i];
}
ans.push_back(product);
return ans;
}
};```

This site uses Akismet to reduce spam. Learn how your comment data is processed.