Product of Array Except Self

Given an integer slice nums, return an array out where out[i] equals the product of all elements except nums[i].

You must run in O(n) time without using division.

Why this is worth learning

Division is unnecessary: every factor except the current element belongs either to its strict left prefix or its strict right suffix. The empty product is one.

Before coding: one-minute experiment

For [2,0,4], which output can be nonzero, and what is it?

Function signature

func ProductExceptSelf(nums []int) []int

Inputs / outputs

• nums: input slice of integers.
• Return: a new slice out of the same length.

Example

nums = [1,2,3,4]
output = [24,12,8,6]

Reason: at index 2, product of all except 3 is 1*2*4 = 8.

Constraints

• 1 <= len(nums) <= 100_000
• -30 <= nums[i] <= 30
• The product of any prefix or suffix fits in a 32-bit signed integer.
• Use the course's 64-bit Go target. A returned value multiplies a prefix by a suffix, so it can exceed 32-bit range even when each factor fits. Its magnitude is at most 2^62, which fits signed 64-bit arithmetic.

Core idea (near-solution)

Compute prefix products and suffix products without extra arrays:

• out[i] will first store the product of all elements to the left of i.
• Then multiply by the product of all elements to the right of i.

Invariant: after the left-to-right pass, out[i] equals product of nums[0..i-1].

Algorithm (step-by-step)

1. Allocate out of length n.
2. Left pass:
   • Set prefix = 1.
   • For i from 0 to n-1:
     • Set out[i] = prefix.
     • Update prefix *= nums[i].
3. Right pass:
   • Set suffix = 1.
   • For i from n-1 down to 0:
     • Multiply out[i] *= suffix.
     • Update suffix *= nums[i].
4. Return out.

Correctness sketch

Before writing out[i] in the forward pass, prefix equals the product of nums[:i]. Storing prefix before multiplying by nums[i] excludes the current value. In the reverse pass, suffix equals the product of nums[i+1:], so multiplying the stored prefix by suffix includes every other factor exactly once. Then suffix is extended for the next position. Both pass invariants hold initially by the empty-product identity one. After the reverse pass every output has the required product, including cases containing one or multiple zeros.

Trace (hand walkthrough)

Example input:
nums = [1,2,3,4]
output = [24,12,8,6]

Reason: at index 2, product of all except 3 is 1*2*4 = 8.

Walk:
- left products: out=[1,1,2,6] (prefix without self)
- right pass: R=1 -> i=3 out=6*1=6, R=4
- i=2 out=2*4=8, R=12
- i=1 out=1*12=12, R=24
- i=0 out=1*24=24 => [24,12,8,6]

Pitfalls to avoid

• Using division (disallowed and breaks with zeros).
• Forgetting to initialize prefix/suffix to 1.
• Overwriting out[i] before multiplying by the suffix pass.

Debugging lens

Test one zero, two zeros, negative signs, and the singleton [7], whose result is [1]. Updating prefix before assigning out[i] incorrectly includes the current element.

Complexity

• Time: O(n)
• Extra space: O(1) beyond the output slice.

Implementation notes (Go)

• The returned slice is new; the input is not modified.

Reconstruction checkpoint

For [2,0,4], which output can be nonzero, and what is it?

Return to Array & String · Module quiz