LeetCode (Medium) 238. Product of Array Except Self

Description:

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 <= 10<sup>5</sup>

• -30 <= nums[i] <= 30

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

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

To solve this problem in O(n) time and without using the division operation, we'll need to use the concept of prefix and suffix products.

First, let's work through the pseudocode:

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var productExceptSelf = function(nums) {
    // Create array for left side product
    // Create array for right side product
    // Combine both arrays to form answer array
};

Now that we have an idea of how to proceed, let's start working through the coding solution.

var productExceptSelf = function(nums) {
    let answer = []
    let leftProduct = [1]
    let rightProduct = Array(nums.length).fill(1)

    // Create array for left side product
    for (let i = 1; i < nums.length; i++){
        leftProduct[i] = leftProduct[i-1] * nums[i-1]
    }

    // Create array for right side product
    for (let i=nums.length-2; i>= 0; i--){
        rightProduct[i] = rightProduct[i+1] * nums[i+1]
    }

    // Combine both arrays to form answer array
    for (let i = 0; i < nums.length; i++){
        answer[i] = leftProduct[i] * rightProduct[i]
    }
    return answer

};

So there are a few pieces in the code we should make note of:

1. We'll need to create three additional arrays, leftProduct, rightProduct, and answer

   1. leftProduct[i] stores the product of all the elements to the left of nums[i] (excluding nums[i])

   2. rightProduct[i] stores the product of all the elements to the right of nums[i] (excluding nums[i])

   3. answer[i] stores the product of leftProduct[i] and rightProduct[i]

2. Once we have these arrays, we can compute the answer array in O(n) time by setting answer[i] =leftProduct[i] * rightProduct[i]. This is because the product of all the elements in the array except nums[i] is equal to the product of all the elements to the left of nums[i] multiplied by the product of all the elements to the right of nums[i].

Solution Follow-Up:

This algorithm has a time complexity of O(n) and uses O(n) extra space to store the leftProduct and rightProduct arrays. To solve the problem in O(1) extra space complexity, we can modify the above algorithm to compute the answer array in place. (Remember: The output array does not count as extra space for space complexity analysis.)

var productExceptSelf = function(nums) {
    let answer = [1]
    for (let i = 1; i < nums.length; i++){
        answer[i] = answer[i-1] * nums[i-1]
    }
    let right = 1
    for (let i = nums.length-1; i>=0; i--){
        answer[i] *= right
        right *= nums[i]
    }
    return answer
};