Medium Prefix/Suffix Arrays & Strings
In plain English: For each number in the array, compute the product of all the other numbers without using division.
Build prefix products left-to-right, then suffix products right-to-left. result[i] = prefix[i] * suffix[i]. Can be done in one array with two passes to stay O(1) extra space.
Prompt
Given an integer array nums, return an array where each element is the product of all other elements. Solve without using division and in O(n).
Try to write it from scratch before scrolling down.
Solution
def product_except_self(nums):
n = len(nums)
result = [1] * n
# left pass: prefix products
prefix = 1
for i in range(n):
result[i] = prefix
prefix *= nums[i]
# right pass: suffix products
suffix = 1
for i in range(n - 1, -1, -1):
result[i] *= suffix
suffix *= nums[i]
return result
# Test: product_except_self([1,2,3,4]) == [24,12,8,6]
# Test: product_except_self([-1,1,0,-3,3]) == [0,0,9,0,0]