Product of Array Except Self

1. Define the problem

Given an integer array nums, return an array answer such that answer_i is equal to the product of every element of nums except nums_i , without using division. Build a running product from the left and a running product from the right (a prefix and a suffix), and multiply them at each index.

Constraints

2 ≤ nums.length ≤ 10⁵
-30 ≤ nums_i ≤ 30

Example

Inputnums = [1, 2, 3, 4]

Output[24, 12, 8, 6]

Explanation answer₀ = 2*3*4 = 24, answer₁ = 1*3*4 = 12, answer₂ = 1*2*4 = 8, answer₃ = 1*2*3 = 6.

2. Visualize the solution

Multiply a left-to-right product by a right-to-left product

Statusleft-pass

Pass 1 fills each slot with the product of everything before it: [1, 1, 2, 6].

What happens in this step

leftProduct = 1
i=0: result[0] = 1;              leftProduct *= 1 → 1
i=1: result[1] = 1;              leftProduct *= 2 → 2
i=2: result[2] = 2;              leftProduct *= 3 → 6
i=3: result[3] = 6;              leftProduct *= 4 → 24

after pass 1: result = [1, 1, 2, 6]

Step 1 of 3

Steps to visualize

Pass 1: walk left to right, storing the running product of everything before each index into the answer array.
Pass 2: walk right to left, multiplying each answer entry by the running product of everything after that index.
Every index now holds the product of everything except itself.

3. Walk through the code

Walk through the code

Same walkthrough, now with the code. Press Next to move one step and watch which lines run.

Multiply a left-to-right product by a right-to-left product

Statusleft-pass

Pass 1 fills each slot with the product of everything before it: [1, 1, 2, 6].

What happens in this step

leftProduct = 1
i=0: result[0] = 1;              leftProduct *= 1 → 1
i=1: result[1] = 1;              leftProduct *= 2 → 2
i=2: result[2] = 2;              leftProduct *= 3 → 6
i=3: result[3] = 6;              leftProduct *= 4 → 24

after pass 1: result = [1, 1, 2, 6]

Step 1 of 3

4. Solution

Solution

solution.tsTypeScript

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

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

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

  return result;
}

Time: O(n)
Space: O(1) extra, excluding the output array

5. Test cases

Test cases

Input	Expected	Covers
`nums = [1, 2, 3, 4]`	`[24, 12, 8, 6]`	example from the docstring
`nums = [-1, 1, 0, -3, 3]`	`[0, 0, 9, 0, 0]`	a single zero forces most outputs to zero without dividing
`nums = [1, 1, 1, 1]`	`[1, 1, 1, 1]`	every value is one, no change in magnitude
`nums = [3, 5]`	`[5, 3]`	smallest valid input, exactly two elements
`nums = [-1, -1, -1, -1]`	`[-1, -1, -1, -1]`	all-negative values, sign handled correctly
`nums = [0, 4, 0]`	`[0, 0, 0]`	two zeros make every product zero

Product of Array Except Self