Interview challenge · medium · array, prefix-product
Product of Array Except Self
El reto
El enunciado va en inglés, igual que en el vídeo.
Given an integer array nums, return an array answer where answer[i] is the product of every element of nums except nums[i]. Do it without division and in O(n) time.
Example
[1, 2, 3, 4] -> [24, 12, 8, 6]
[-1, 1, 0, -3, 3] -> [0, 0, 9, 0, 0]Idea: the answer at i is (product of everything to the left) times (product of everything to the right). A first pass writes the left products; a second pass, from the right, multiplies in the right products with a running total. Time O(n), space O(1) besides the output.
La solución
# Product of Array Except Self - ayotl.dev
def except_self(nums):
out = [1] * len(nums)
# left pass: product before i
acc = 1
for i in range(len(nums)):
out[i] = acc
acc *= nums[i]
# right pass: times product after i
acc = 1
for i in reversed(range(len(nums))):
out[i] *= acc
acc *= nums[i]
return out
print(except_self([1, 2, 3, 4]))
print(except_self([-1, 1, 0, -3, 3]))
$ python3 product_of_array_except_self.py
[24, 12, 8, 6]
[0, 0, 9, 0, 0]