Product of Array Except Self

Problem

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

 

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

 

Constraints:

• 2 <= nums.length <= 105
• -30 <= nums[i] <= 30
• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const leftProduct = [1];
    const rightProduct = [1];
    for (let i = 0; i < nums.length; i++) {
        leftProduct.push(leftProduct[i] * nums[i]);
        rightProduct.push(rightProduct[i] * nums[nums.length - 1 - i]);
    }

    const res = [];
    for (let i = 0; i < nums.length; i++) {
        res.push(leftProduct[i] * rightProduct[nums.length - 1 - i]);
    }
    return res;
};

Notice that res[i] = sum(nums[0:i]) * sum(nums[i + 1:nums.length]). Thus, we can first calculate left[i] as the product of values starting from the left of nums, and right[i] as the product of values starting from the right of nums beforehand in O(n). Note that we use 1 as the first value in both arrays, and don't include the final value (ie. ignore nums[nums.length - 1] for left and ignore nums[0] for right). Using left and right, we get that res[i] = left[i] * right[nums.length - 1 - i].

Follow-up

Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Solution

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    const res = [];

    let leftProduct = 1;
    for (let i = 0; i < nums.length; i++) {
        res.push(leftProduct);
        leftProduct *= nums[i];
    }

    let rightProduct = 1;
    for (let i = nums.length - 1; i >= 0; i--) {
        res[i] *= rightProduct;
        rightProduct *= nums[i];
    }

    return res;
};

To use only O(1) extra space, we store left in our output array res. Next, we use a single variable to accumulate the values of right, while directly using it to compute the answer res.

For example, let nums = [4, 3, 2, 1]. After the first loop, res = [1, 1 * 4, 1 * 4 * 3, 1 * 4 * 3 * 2] = [1, 4, 12, 24]. After the second loop, res = [1 * 3 * 2 * 1 * 1, 4 * 2 * 1 * 1 , 12 * 1 * 1 , 24 * 1] = [6, 8, 12, 24].