Product of Array Except Self

Given an array of

nintegers wheren> 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 divisionand in O(n).For example, given

`[1,2,3,4]`

, return`[24,12,8,6]`

.

Follow up:

Could you solve it with constant space complexity? (Note: The output arraydoes notcount 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; } };