Product of Array Except Self

For each position, return the product of all other values. Do not use division.

Start with the concrete trace below. It shows the state the algorithm must carry as it runs.

Problem trace

Product of Array Except Self: At index i, combine the product strictly before i with the product strictly after i.

Input and goalFor each position, return the product of all other values. Do not use division.

Initialize the prefix passFor nums = [1, 2, 3, 4], output starts as [1, 1, 1, 1] and prefix starts at 1.

prefix i=0num 1 / out 10num 2 / out 11num 3 / out 12num 4 / out 13

phaseleft to rightprefix1operationready to write out[0]

Recognize it

Each output excludes exactly one array position, division is forbidden, and multiplication can be accumulated from either boundary.

Keep true

Before prefix index i, prefix is the product of nums[0..i-1]. Before suffix index i, suffix is the product of nums[i+1..n-1], while out[i] already stores the left product.

Reuse it

When every answer excludes one position and the operation is associative, save the contribution from one side and sweep the other side with a scalar; the same decomposition works for left/right minima, maxima, and cumulative constraints.

Pattern: Prefix and suffix products.

Simple idea: The answer at one position is the product on its left times the product on its right. First save every left product. Then multiply by each right product.

def product_except_self(nums: list[int]) -> list[int]:
   answer = [1] * len(nums)

   prefix = 1
   for index, num in enumerate(nums):
      answer[index] = prefix
      prefix *= num

   suffix = 1
   for index in range(len(nums) - 1, -1, -1):
      answer[index] *= suffix
      suffix *= nums[index]

   return answer

Cost: $O(n)$ time and $O(1)$ extra space, not counting the answer.