Product of Array Except Self
Return an array answer where answer[i] equals the product of all elements of nums except nums[i]. Solve in O(n) without using division.
Answers use simple, clear English.
Audio N/AQuick interview answer
Build prefix products left-to-right, then multiply by a running suffix from the right into the output array. Two linear passes, no division, O(1) extra besides the output.
Detailed answer
Build prefix products left-to-right, then multiply by a running suffix from the right into the output array. Two linear passes, no division, O(1) extra besides the output. Division fails on zeros and is usually disallowed. Clarify whether output space counts toward space complexity.
Full explanation
Division fails on zeros and is usually disallowed. Clarify whether output space counts toward space complexity.
Real example & use case
Analytics dashboard showing contribution of each metric while excluding that metric from a composite score.
Pros & cons
Pros: O(n), interview classic. Cons: careful indexing; overflow in fixed-width ints.
Code example
def product_except_self(nums: list[int]) -> list[int]:
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 outPractice code · python (view only · no execution)
def product_except_self(nums: list[int]) -> list[int]:
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 out