Products of Array Except Self

Problem

Given an integer array nums, return an array output where output[i] is the product of all the elements of nums except nums[i].

Each product is guaranteed to fit in a 32-bit integer.

Follow-up: Could you solve it in O(n) time without using the division operation?

Examples

Example 1:

Input: nums = [1,2,4,6]

Output: [48,24,12,8]

Example 2:

Input: nums = [-1,0,1,2,3]

Output: [0,-6,0,0,0]

Constraints

• 2 <= nums.length <= 1000
• -20 <= nums[i] <= 20

You should aim for a solution as good or better than O(n) time and O(n) space, where n is the size of the input array.

Solution

We cannot just create the product of all items, in one pass, then go back and divide out the item at that index, because a single 0 will taint the entire product.

Instead, we use 2 arrays. One tracks the prefix product and one tracks the suffix product.

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        // Solution 2
        // Use 2 arrays, one which tracks prefix product and one that tracks suffix product
        //   result[i] is simply the product of prefix[i] * suffix[i]. Since none of these contain
        //   the actual value of nums[i], we dont get the pollution of multiplying by zero
        std::vector<int> prefix_prod(nums.size(), 1);
        for (std::size_t i = 1; i < nums.size(); ++i) {
            prefix_prod[i] = prefix_prod[i-1] * nums[i-1];
        }
        std::vector<int> suffix_prod(nums.size(), 1);
        for (std::size_t i = 1; i < nums.size(); ++i) {
            auto idx = nums.size() - 1 - i;
            suffix_prod[idx] = suffix_prod[idx+1] * nums[idx+1];
        }
        std::vector<int> result(nums.size());
        for (std::size_t i = 0; i < nums.size(); ++i) {
            result[i] = prefix_prod[i] * suffix_prod[i];
        }
        return result;
    }
};