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.

Solving with Two Arrays

To solve the problem, we can use two arrays: one to store the left products and another to store the right products. The product at each index is calculated by multiplying the products before and after that index.

prod = (left products) X (right products);

First, let’s focus on the left product. Assuming we have an array called nums with values [0, 1, 2, 3], here’s how the left products would look for each index:

left[1] = 0;
left[2] = 0 * 1;
left[3] = 0 * 1 * 2;

We can observe that the left product at index i is equal to the product of the left product at index i-1 multiplied by the number at index i-1. Therefore:

left[i] = left[i-1] * nums[i-1];

We can use a similar concept to generate the right products:

right[i] = right[i+1] * nums[i+1];

Finally, to get the product at a specific index i, we multiply the corresponding left and right products:

prod[i] = left[i] * right[i];

Here’s the code:

var productExceptSelf = function(nums) {
  const left = [1];
  for (let i = 1; i < nums.length; i++) {
    left[i] = nums[i-1] * left[i-1];
  }

  const right = [];
  right[nums.length-1] = 1;
  for (let i = nums.length - 2; i >= 0; i--) {
    right[i] = nums[i+1] * right[i+1];
  }

  const res = [];
  for (let i = 0; i < nums.length; i++) {
    res[i] = left[i] * right[i];
  }

  return res;
};

This solution has a time and space complexity of O(N).

Optimizing Space

The problem has a 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.)

We used two arrays to hold the left and right products, and we need to solve the problem without using these arrays.

The output array does not count as extra space, so we can utilize it to temporarily store the left or right products. In this case, let’s use the output array to hold the left products.

Now that we have handled the left products, let’s figure out how to calculate the right products. Given the example array nums = [0, 1, 2, 3], the right products can be calculated as follows:

right[2] = 3;
right[1] = 3 * 2;
right[0] = 3 * 2 * 1;

We can observe that the right product can be obtained by multiplying the current right product with the number at the next index. Therefore:

right = 3;
right = right * 2;
right = right * 1;
...
right = right * nums[i+1];

By using a single variable right, we can calculate the right products without using an additional array, resulting in O(1) space complexity.

Here’s the code for the optimized solution:

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

This optimized solution still maintains O(N) time complexity but reduces the space complexity to O(1).