Product of Array Except Self

The problem

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

Function: def productExceptSelf(nums):

Example input (a JSON list of arguments): [[1, 2, 3, 4]]
Expected output: [24, 12, 8, 6]

Inputs satisfy the problem statement. Sequences contain at most 200 elements unless a smaller bound is stated. Use JSON values and the supplied function signature.

Hints

1. Store the product strictly before each position, then multiply by a running suffix product.
2. Check the supplied examples, empty/boundary cases and the stated answer policy before optimizing.

Worked answer

Try it yourself first. When you are ready, open the answer below.

def productExceptSelf(nums):
    out=[1]*len(nums); product=1
    for i,n in enumerate(nums): out[i]=product; product*=n
    product=1
    for i in range(len(nums)-1,-1,-1): out[i]*=product; product*=nums[i]
    return out

Why it works

Store the product strictly before each position, then multiply by a running suffix product. Division is unnecessary, so one or multiple zeroes are handled naturally.

Complexity: O(n) time / O(1) extra space excluding result.

Time: O(n) time · Space: O(1) extra space excluding result