Product of Array Except Self

Difficulty: Medium

You're given a list of numbers. Build a new list where each position holds the product of all the other numbers in the original list - everything except the number that sits at that position.

You need to do this without using division anywhere (even though "total product divided by nums[i]" is a tempting shortcut, it breaks down whenever the list contains a zero).

Examples

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

For index 0: 234 = 24. For index 1: 134 = 12. And so on for each position.

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

Every position except index 2 includes the 0 from the list in its product, so it comes out to 0. Index 2 excludes that 0, leaving -1 * 1 * -3 * 3 = 9.

Constraints

2 <= nums.length <= 10^5
The product of any prefix or suffix of nums fits in a standard integer range.
You may not use the division operator.

Approach

The direct way to think about this problem: the answer at each position is the product of everything to its left, times the product of everything to its right. A brute-force solution recomputes that whole product from scratch for every single position, which means redoing a lot of the same multiplication over and over.

The efficient version reuses work across positions instead of recomputing it. In one left-to-right pass, store at each position the running product of everything that came before it. Then, in a second right-to-left pass, multiply in the running product of everything that comes after it. By the end, every position holds exactly the product of all the other numbers, and division never enters the picture.

Solutions

Brute Force - Recompute Each Product

For every position, loop through the entire list again and multiply together every number except the one at that position.

function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);

  for (let i = 0; i < n; i++) {
    let product = 1;
    for (let j = 0; j < n; j++) {
      if (j !== i) {
        product *= nums[j];
      }
    }
    result[i] = product;
  }

  return result;
}

Time: O(n²) · Space: O(1) extra space, beyond the output array

Optimal - Prefix and Suffix Products

In one left-to-right pass, fill the output array with the running product of everything before each position. Then, in a right-to-left pass, multiply in the running product of everything after each position. Combining both gives, for every index, the product of all the other numbers.

function productExceptSelf(nums) {
  const n = nums.length;
  const result = new Array(n).fill(1);

  let prefix = 1;
  for (let i = 0; i < n; i++) {
    result[i] = prefix;
    prefix *= nums[i];
  }

  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    result[i] *= suffix;
    suffix *= nums[i];
  }

  return result;
}

Time: O(n) · Space: O(1) extra space, beyond the output array