Product of everything else
Write product_except_self(nums) that returns a list where each item is the product of every other item. Do it in O(n) without using division.
product_except_self([1, 2, 3, 4]) # [24, 12, 8, 6]
product_except_self([0, 1, 2]) # [2, 0, 0]Show hint
The answer at position i is (product of everything to the left) × (product of everything to the right). You can compute both in two passes.
Show solution
def product_except_self(nums):
n = len(nums)
out = [1] * n
left = 1
for i in range(n):
out[i] = left
left *= nums[i]
right = 1
for i in range(n - 1, -1, -1):
out[i] *= right
right *= nums[i]
return outThe first pass stores the product of everything to the left of each position, and the second multiplies in everything to the right. Dividing the total product by each item would fail as soon as the list contains a zero, which is why the problem bans division.
Want a problem like this every day? See today's problem and keep a streak going.