Product of Array Except Self

1. The obvious way

   For each position multiply all the others: O(n²). Dividing the total by the number fails with zeros and is not allowed.

2. The key insight

   Walk left to right writing, at each position, the product of everything before it (carrying a running product). Walk right to left multiplying each position by the product of everything after it (another running product). No division and no extra lists.

3. The algorithm
   1. Make the answer list, all ones. Start a running product at 1.
   2. Walk left to right: write the running product into the answer, then multiply the running product by the current number.
   3. Reset the running product to 1. Walk right to left: multiply the answer by the running product, then update the running product the same way.

Watch it run

left products: [1, 1, 2, 6]

def product_except_self(nums):
    answer = [1] * len(nums)
    running = 1
    for position in range(len(nums)):              # left to right
        answer[position] = running                 # product of everyone before
        running *= nums[position]
    running = 1
    for position in range(len(nums) - 1, -1, -1):  # right to left
        answer[position] *= running                # times everyone after
        running *= nums[position]
    return answer

Now close this and write it again from memory, in the language you will use in the interview. Reattempt after 1 day, 7 days and about 30 days.