Product of Array Except Self

def productExceptSelf(nums):
    n = len(nums)
    answer = [1] * n
    left = 1
    for i in range(n):
        answer[i] = left      # store
        left *= nums[i]       # pick up
    right = 1
    for i in range(n - 1, -1, -1):
        answer[i] *= right    # multiply in
        right *= nums[i]      # pick up
    return answer

Product of Array Except Self. Given a list of numbers, return a list where each spot holds the product of all the other numbers, in linear time and without division.

Take one, two, three, four. Skip the first, and two times three times four is twenty-four. Skip the second: twelve. Then eight, and six.

Multiplying all the others for every spot is n squared work. Dividing the total by each number is banned, and a single zero would break it anyway: the total becomes zero, and you can't divide by zero.

Here's the trick. Everything except one spot splits in two: the numbers on its left, and the numbers on its right. Send a beam in from the left that multiplies as it passes each number, and another from the right. Each spot multiplies what reaches it from both sides.

In code, the answer starts as ones. The first loop goes left to right: store the running product, then multiply in the number. The second loop goes right to left with a new running product: multiply it into the answer, then multiply in the number.

Let's run it. From the left, the beam leaves one, one, two, and six: the product before each spot. Now from the right, starting at one. The last spot: six times one, six. The beam picks up four: two times four, eight. Then twelve: one times twelve, twelve. Then twenty-four. The answer: twenty-four, twelve, eight, six.

Two passes, so the time is linear. Besides the output, we keep one running number: constant extra space.

Left times right, no division. That's Product of Array Except Self.