[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].

Follow up:
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;
    }
};

 

Leave a comment

Your email address will not be published.

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