Return an array where each element is the product of all other elements, without using division.
Make two passes: a left pass where each position accumulates the product of everything to its left, then a right pass (using a rolling variable) that multiplies in everything to its right. The two passes together give the complete product-of-all-others in O(n) time and O(1) extra space (excluding output).
How to think about it
The “no division” clause is the whole interview. It quietly bans the slick answer — multiply everything into one total, then divide it by each element — and forces you to think about what result[i] actually is. The product of everything except i splits cleanly into two independent pieces: everything to the left of i, and everything to the right of i. Two independent products mean two passes.
So you build them in turn. In the first pass, walk left to right and store in result[i] the product of all elements strictly to its left, seeding with 1 because nothing sits left of index 0. In the second pass, walk right to left carrying a single rolling variable right_prod that holds the product of everything to the right so far; multiply it into result[i], then fold nums[i] into right_prod for the next step. After both passes, each slot holds left-product times right-product — exactly the product of all others — and you never allocated a second array. Zeros need no special case: a zero simply propagates into the left or right product of its neighbours.
A worked example
def product_except_self(nums):
n = len(nums)
result = [1] * n
# pass 1: each slot gets the product of everything to its LEFT
left_prod = 1
for i in range(n):
result[i] = left_prod
left_prod *= nums[i]
# pass 2: multiply in everything to the RIGHT via one rolling variable
right_prod = 1
for i in range(n - 1, -1, -1):
result[i] *= right_prod
right_prod *= nums[i]
return result
print(product_except_self([1, 2, 3, 4])) # the clean case
print(product_except_self([-1, 1, 0, -3, 3])) # a single zero
print(product_except_self([0, 0])) # two zeros
print(product_except_self([5])) # single element[24, 12, 8, 6]
[0, 0, 9, 0, 0]
[0, 0]
[1]Read [1, 2, 3, 4]. After pass one, result holds the left products [1, 1, 2, 6]; pass two folds in the right products [24, 12, 4, 1], and the elementwise product is [24, 12, 8, 6] — each entry is the other three multiplied. The zero cases confirm the claim that zeros take care of themselves: with one zero only its own index survives non-zero (9, the product of the rest), and with two zeros everything collapses to 0 — no special-casing written anywhere.