Product of Array Except Self

Learning goal: Recognize what each output position must include and why a direct total-product shortcut is unsafe.

Core idea At index i, the answer must exclude exactly one value: nums[i]. Everything else naturally splits into two independent groups, the values before i and the values after i. Therefore, answer[i] is the product of a left region and a right region.

Algorithm plan

• Read the input as two regions around each index.
• Combine the left product with the right product.
• Avoid division so zeros require no special case.

Micro-example For [1, 2, 3, 4], index 2 contains 3. The left product is 1 × 2 = 2; the right product is 4, so the answer is 8.

Pitfalls

• The current element must not be included in its own answer.
• A total-product division approach is invalid when an element is zero.
• Empty left or right regions should contribute the multiplicative identity 1.

Recap

• Each answer is left product × right product.
• The identity product 1 handles array boundaries.
• No division is needed.

Learning goal: See how every answer can be assembled from two running products.

Core idea A prefix product summarizes everything encountered from the left. A suffix product summarizes everything encountered from the right. If we place the prefix product into output[i] before multiplying by the suffix product, the same output slot becomes the complete answer.

Algorithm plan

• During the left-to-right pass, write the product strictly before i into output[i].
• During the right-to-left pass, multiply output[i] by the product strictly after i.
• Update the running product only after using the current slot.

Micro-example For [1, 2, 3, 4], the first pass writes [1, 1, 2, 6]. The reverse pass multiplies by suffix products 1, 4, 12, 24 in reverse position order.

Pitfalls

• Updating prefix before writing would include nums[i] incorrectly.
• Updating suffix before multiplying would include nums[i] incorrectly.
• The output array is allowed to be scratch space; a separate prefix array is unnecessary.

Recap

• Left sweep supplies the prefix side.
• Right sweep supplies the suffix side.
• The output array stores intermediate values safely.

Learning goal: Translate the prefix/suffix idea into a correct linear-time algorithm.

Core idea Initialize prefix and suffix to 1, the identity for multiplication. The first sweep fills output[i] with the product of all earlier values, then extends prefix with nums[i]. The second sweep runs backward, multiplies the current slot by suffix, and only then extends suffix with nums[i].

Algorithm plan

1. Create output with the same length as nums.
2. Set prefix = 1.
3. For i from left to right, write output[i] = prefix, then set prefix *= nums[i].
4. Set suffix = 1.
5. For i from right to left, set output[i] *= suffix, then suffix *= nums[i].
6. Return output.

prefix = 1
for i in range(n):
    output[i] = prefix
    prefix *= nums[i]

suffix = 1
for i in range(n - 1, -1, -1):
    output[i] *= suffix
    suffix *= nums[i]

Micro-example At index 3, the left pass stores 1 × 2 × 3 = 6. The reverse pass uses an empty right region, so it multiplies by 1; the answer remains 6.

Pitfalls

• The reverse loop must include index 0.
• Use the current value after writing or multiplying the slot.
• Do not allocate prefix and suffix arrays if O(1) extra space is required.

Recap

• Two passes cover both sides of every index.
• Each pass performs constant work per element.
• The returned array doubles as scratch space.

Learning goal: Trace both passes and verify every intermediate value on one complete example.

Core idea The left pass establishes a promise for each slot: it contains the product of all values before that index. The right pass preserves that prefix information while multiplying in the product of all values after the index. At the end, each slot has exactly the two regions it needs.

Algorithm plan

• Start with prefix = 1 and scan indices 0 through 3.
• Store the current prefix before extending it.
• Start with suffix = 1 and scan indices 3 through 0.
• Multiply first, then extend the suffix.

Micro-example Left pass: [1, 1, 2, 6]. Right pass: index 3 stays 6, index 2 becomes 8, index 1 becomes 12, and index 0 becomes 24.

Pitfalls

• At index 0, the left side is empty and contributes 1.
• At index 3, the right side is empty and contributes 1.
• Do not confuse the running product with the value currently stored in output[i].

Recap

• The first pass produces prefix-only values.
• The second pass completes them with suffix products.
• The final array is [24, 12, 8, 6].

Learning goal: Explain why division is the wrong shortcut and verify that the two-pass method handles zeros.

Core idea Dividing the total product by nums[i] appears short, but it fails immediately when nums[i] is zero. Even special-casing one zero becomes awkward with multiple zeros. The two-sweep method never divides and simply lets zero flow into every product that should contain it.

Algorithm plan

• Use 1 for an empty side of the array.
• Write or multiply before updating the running product.
• Treat negative values exactly like positive values; multiplication already handles the sign.
• Test arrays containing zero, multiple zeros, and negative numbers.

Micro-example For [0, 2, 3, 4], index 0 gets 2 × 3 × 4 = 24. Every other index has the zero on one side, so its answer is 0.

Pitfalls

• A zero must not be “removed” through division.
• Multiple zeros should produce an all-zero result.
• Negative values can make the result negative, but require no algorithm change.

Recap

• No division means zero handling is automatic.
• Empty sides contribute 1.
• Update running products after using the current index.

Learning goal: Justify the target complexity and retain the core invariant for implementation.

Core idea The algorithm visits every element once from the left and once from the right. Each visit performs a constant number of multiplications and assignments. Apart from the returned output array, it stores only prefix, suffix, and a loop index.

Algorithm plan

• Allocate the required output array of length n.
• Count the left sweep as O(n).
• Count the right sweep as O(n).
• Treat the output array as the required result, not as extra working memory.

Micro-example For n = 4, there are four prefix writes and four suffix multiplications. The work grows proportionally with n, rather than comparing every pair of positions.

Pitfalls

• Do not count the returned output array as O(n) extra space for this problem's convention.
• A separate prefix or suffix array would raise auxiliary space to O(n).
• Nested loops would lose the linear-time guarantee.

Recap

• Time: O(n).
• Extra space: O(1) beyond the output array.
• Invariant: each slot becomes left product × right product.