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.

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.

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

• Invariant: after the left-to-right pass, out[i] equals product of nums[0..i-1].
• prefix[i] is the product of elements left of i, and suffix[i] is right of i.
• Multiplying them yields the product of all elements except i.
• This holds for every index, so the output array is correct.

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.

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.