Module 06 · Prefix Sums, Prefix State, and Difference Arrays

057. Product Except Self

Bridge · Download this solution · All solutions and shared helpers

Problem

Return a list where output[i] is the product of every input value except nums[i], without division. Integers may include zero and negatives. Empty input returns []; a singleton returns [1], the empty product. Do not modify nums.

Examples

Example 1

product_except_self([1, 2, 3, 4])
=> [24, 12, 8, 6]

Each answer combines the two strict sides.

Example 2

product_except_self([0, 2, 3])
=> [6, 0, 0]

Only the zero position excludes the zero factor.

Example 3

product_except_self([9])
=> [1]

The product of no remaining values is one.

Reveal the worked solution and reasoning

Why this mechanism works

Split each answer into the product strictly to its left and strictly to its right. Store left products in the output, then multiply by a running right product in reverse order. Zero requires no special branch because multiplication handles it naturally.

State and boundaries

left is the product before i in the forward pass. right is the product after i in the backward pass.

Protocol

Initialize output entries to one.
Commit the current left product before multiplying in nums[i].
Scan backward.
Multiply output[i] by the current right product before extending right.

Visualization

nums:   1 2 3 4
left:   1 1 2 6
right: 24 12 4 1
answer:24 12 8 6

Python implementation

def product_except_self(nums):
    output = [1] * len(nums)
    left = 1
    for i, value in enumerate(nums):
        output[i] = left
        left *= value
    right = 1
    for i in range(len(nums) - 1, -1, -1):
        output[i] *= right
        right *= nums[i]
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

product_except_self([1, 2, 3, 4])

L2 product_except_self: output = [1] * len(nums)
nums=[1, 2, 3, 4]; output=[1, 1, 1, 1]

L3 product_except_self: left = 1
nums=[1, 2, 3, 4]; output=[1, 1, 1, 1]; left=1

L4 product_except_self: for i, value in enumerate(nums):
nums=[1, 2, 3, 4]; output=[1, 1, 1, 1]; left=1; i=0; value=1

L4 product_except_self: for i, value in enumerate(nums):
nums=[1, 2, 3, 4]; output=[1, 1, 1, 1]; left=1; i=1; value=2

L6 product_except_self: left *= value
nums=[1, 2, 3, 4]; output=[1, 1, 1, 1]; left=2; i=1; value=2

L4 product_except_self: for i, value in enumerate(nums):
nums=[1, 2, 3, 4]; output=[1, 1, 1, 1]; left=2; i=2; value=3

L5 product_except_self: output[i] = left
nums=[1, 2, 3, 4]; output=[1, 1, 2, 1]; left=2; i=2; value=3

L6 product_except_self: left *= value
nums=[1, 2, 3, 4]; output=[1, 1, 2, 1]; left=6; i=2; value=3

... 9 intermediate state changes omitted ...

L9 product_except_self: output[i] *= right
nums=[1, 2, 3, 4]; output=[1, 12, 8, 6]; left=24; i=1; value=4; right=12

L10 product_except_self: right *= nums[i]
nums=[1, 2, 3, 4]; output=[1, 12, 8, 6]; left=24; i=1; value=4; right=24

L8 product_except_self: for i in range(len(nums) - 1, -1, -1):
nums=[1, 2, 3, 4]; output=[1, 12, 8, 6]; left=24; i=0; value=4; right=24

L9 product_except_self: output[i] *= right
nums=[1, 2, 3, 4]; output=[24, 12, 8, 6]; left=24; i=0; value=4; right=24

Result: [24, 12, 8, 6]. Each answer combines the two strict sides.

product_except_self([0, 2, 3])

L2 product_except_self: output = [1] * len(nums)
nums=[0, 2, 3]; output=[1, 1, 1]

L3 product_except_self: left = 1
nums=[0, 2, 3]; output=[1, 1, 1]; left=1

L4 product_except_self: for i, value in enumerate(nums):
nums=[0, 2, 3]; output=[1, 1, 1]; left=1; i=0; value=0

L6 product_except_self: left *= value
nums=[0, 2, 3]; output=[1, 1, 1]; left=0; i=0; value=0

L4 product_except_self: for i, value in enumerate(nums):
nums=[0, 2, 3]; output=[1, 1, 1]; left=0; i=1; value=2

L5 product_except_self: output[i] = left
nums=[0, 2, 3]; output=[1, 0, 1]; left=0; i=1; value=2

L4 product_except_self: for i, value in enumerate(nums):
nums=[0, 2, 3]; output=[1, 0, 1]; left=0; i=2; value=3

L5 product_except_self: output[i] = left
nums=[0, 2, 3]; output=[1, 0, 0]; left=0; i=2; value=3

... 3 intermediate state changes omitted ...

L10 product_except_self: right *= nums[i]
nums=[0, 2, 3]; output=[1, 0, 0]; left=0; i=1; value=3; right=6

L8 product_except_self: for i in range(len(nums) - 1, -1, -1):
nums=[0, 2, 3]; output=[1, 0, 0]; left=0; i=0; value=3; right=6

L9 product_except_self: output[i] *= right
nums=[0, 2, 3]; output=[6, 0, 0]; left=0; i=0; value=3; right=6

L10 product_except_self: right *= nums[i]
nums=[0, 2, 3]; output=[6, 0, 0]; left=0; i=0; value=3; right=0

Result: [6, 0, 0]. Only the zero position excludes the zero factor.

Why the solution is correct

The forward pass writes exactly the factors with indices smaller than i. The backward pass supplies exactly the greater indices. These disjoint factor sets exclude only i, and their product is the required answer even when some factors are zero.

Time and space

O(n) arithmetic operations; O(n) output and O(1) other state. Large integer products may have nonconstant arithmetic cost.

Common mistakes

Updating a side product before committing includes the value that must be excluded. Division is both prohibited and problematic at zero.

Reasoning card

State: left is the product before i in the forward pass. right is the product after i in the backward pass.

Invariant: Before the reverse pass, output[i] equals product strictly left of i.

Decision to rehearse: Commit left products, then multiply by a rolling right product.

Finish: Multiply output[i] by the current right product before extending right

Transfer exercise

Generalize the two-sided aggregation to an associative operation and specify its identity element.