Product of Array Except Self
Build an array where position i holds the product of every value in nums except nums[i], without division.
Intuition
Multiplying every other element separately for each output repeats almost the same work O(n²) times. For index i, the needed factors naturally split into everything left of i and everything right of i. A forward pass can place the product of the left side into the answer, and a backward pass can multiply in a running product of the right side. Because each running product is used before the current value is included, nums[i] is excluded automatically, including when zeros are present.
When each output combines all elements except the current one, look for a left contribution and a right contribution. Prefix and suffix accumulation avoids rebuilding those two ranges for every index and avoids the problems division has with zero.
Approach
Write each index's left product
Start prefix at 1, the product of an empty side. At index i, store the current prefix in answer[i], then multiply prefix by nums[i] for the next position. Using the value before updating is what excludes the current element.
Sweep backward with the right product
Start suffix at 1 and move from the final index toward zero. Multiply answer[i] by the current suffix, which contains only values strictly to the right, then include nums[i] in the suffix for the next index.
Let multiplication handle zeros naturally
No division or zero counting is necessary. With one zero, only its own position receives the product of the non-zero sides; with multiple zeros, every output receives a zero from at least one side. Both passes are linear and use only running variables beyond the output.
Solution
Common pitfalls
Using division despite zero values
answer[i] = total_product // nums[i]
answer[i] = prefix
Division is forbidden and becomes undefined at zero; separate side products work for every input.
Including the current number in the prefix
prefix *= nums[i] answer[i] = prefix
answer[i] = prefix prefix *= nums[i]
Updating first puts nums[i] into its own output, which violates the except-self requirement.
Updating the suffix before using it
suffix *= nums[i] answer[i] *= suffix
answer[i] *= suffix suffix *= nums[i]
The suffix must represent positions strictly to the right when it is multiplied into answer[i].
Edge cases
[1, 2, 0, 4]The zero index combines non-zero prefix and suffix products, while every other position receives zero from one side.
Every index has a zero on its left or right, so both passes correctly produce all zeros.
Prefix and suffix multiplication preserve signs without any special branch.