Overview

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

Implement productExceptSelf(nums).

Constraints

• Input is an array with at least 2 elements.
• You must not use division.
• Aim for $O(n)$ time complexity.
• Aim for $O(1)$ extra space (the output array doesn't count).
• The product of any prefix or suffix of nums fits in a 32-bit integer.

Examples

productExceptSelf([1, 2, 3, 4]);    // [24, 12, 8, 6]
productExceptSelf([-1, 1, 0, -3, 3]); // [0, 0, 9, 0, 0]
productExceptSelf([2, 3]);           // [3, 2]

Notes

• The key insight: output[i] = (product of all elements to left of i) * (product of all elements to right of i).
• Two-pass approach: first pass computes prefix products (left-to-right), second pass multiplies in suffix products (right-to-left).
• This avoids division entirely and runs in $O(n)$ with $O(1)$ extra space (using the output array to store prefix products, then multiplying suffix in-place).

Solution

function productExceptSelf(nums) {
  const n = nums.length;
  const output = new Array(n);

  // Left pass: output[i] = product of all elements to the left of i
  output[0] = 1;
  for (let i = 1; i < n; i++) {
    output[i] = output[i - 1] * nums[i - 1];
  }

  // Right pass: multiply in the product of all elements to the right
  let right = 1;
  for (let i = n - 1; i >= 0; i--) {
    output[i] *= right;
    right *= nums[i];
  }

  return output;
}

Resources

• Product of Array Except Self — LeetCode
• Prefix Sum Pattern