238. Product of Array Except Self

Return an array answer where answer[i] is the product of all elements of nums except nums[i], in O(n) time without using division.

Store prefix products in the output, then sweep right to left with a running suffix product.

1function productExceptSelf(nums: number[]): number[] {
2  const n = nums.length, out = new Array(n).fill(1);
3  for (let i = 1; i < n; i++) out[i] = out[i - 1] * nums[i - 1];
4  let suffix = 1;
5  for (let i = n - 1; i >= 0; i--) {
6    out[i] *= suffix;
7    suffix *= nums[i];
8  }
9  return out;
10}

nums

out

out starts as all 1s.

1 / 0

Space: play/pause · ←/→: step