Product of Array Except Self

The product of everything except index i splits cleanly into two independent pieces: the prefix product of everything to its left, and the suffix product of everything to its right. Computing running prefix products left-to-right and running suffix products right-to-left assembles the answer for every cell without ever needing arithmetic division.

Full solution

Single output array two-pass accumulation: a forward sweep fills prefix products into the answer, then a backward sweep multiplies in a running suffix product. Linear time, no division, and no extra array beyond the output.

from typing import List


def product_except_self(nums: List[int]) -> List[int]:
    n = len(nums)
    answer = [1] * n
    prefix = 1
    for i in range(n):
        answer[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= suffix
        suffix *= nums[i]
    return answer

function productExceptSelf(nums) {
  const n = nums.length;
  const answer = new Array(n).fill(1);
  let prefix = 1;
  for (let i = 0; i < n; i++) {
    answer[i] = prefix;
    prefix *= nums[i];
  }
  let suffix = 1;
  for (let i = n - 1; i >= 0; i--) {
    answer[i] *= suffix;
    suffix *= nums[i];
  }
  return answer.map((v) => (v === 0 ? 0 : v)); // normalize -0 to 0
}

The theory behind it

Arrays — the ground this problem stands on. All Arrays problems

What Arrays is

An array is a row of fixed boxes laid side by side in computer memory, like numbered lockers in a hallway. Because each box occupies identical space and sits directly next to its neighbors, jumping to locker zero or locker ten thousand takes the exact same tiny fraction of time. Every box holds an item of the same type, addressed by an offset number called an index.

When to reach for it

Reach for an array when items arrive in a known sequence and need immediate retrieval by position number. Problems asking for running totals, prefix accumulations, cyclic rotations, or in-place rearrangements signal array mechanics. Whenever constraints require constant-time random lookups or contiguous cache scans across fixed collections, a flat sequence is the default container.

How the pattern works

Visualize a tape with zero-indexed slots stretching from start to end. Keep track of write and read cursors when modifying contents without allocating helper buffers. For running computations, maintain an invariant such as having processed all elements left of the current index while pending elements wait to the right. When modifying entries in place, consider scanning backwards from the end so unread data is not overwritten.