Product Except Self

The Idea

The answer at index i is everything to its left multiplied by everything to its right. So make two sweeps. Going left to right, write the running product of the left side into the output, before folding the current value in. Then sweep back, multiplying in the running product of the right side. Each cell meets both halves of the array without ever meeting itself.

Real-World Example

A production line reports the yield of each stage, and management wants, per stage, the combined yield of all the others — the number that says what the line would do if that stage were perfect. One walk down the line and one walk back gives every stage its figure.

The Code

def product_except_self(nums):
    out = [1] * len(nums)
    prefix = 1
    for i in range(len(nums)):              # everything left of i
        out[i] = prefix
        prefix *= nums[i]
    suffix = 1
    for i in range(len(nums) - 1, -1, -1):  # fold in everything right of i
        out[i] *= suffix
        suffix *= nums[i]
    return out

print(product_except_self([2, 3, 4, 5]))   # [60, 40, 30, 24]

nums = [1, 2, 3]
out = [1, 1, 1]
p = 1
for i in range(3):
  out[i] = p
  p *= nums[i]
print(out)