25 lines
825 B
Python
25 lines
825 B
Python
|
from functools import reduce
|
||
|
|
|
||
|
|
class Solution:
|
||
|
|
def productExceptSelf(self, nums: List[int]) -> List[int]:
|
||
|
|
# We can divide this problem by finding the prefix and
|
||
|
|
# postfix products of a given element and then multiplying
|
||
|
|
# them together
|
||
|
|
result = [0] * len(nums)
|
||
|
|
|
||
|
|
# Find prefix products, i.e, for ith element, store
|
||
|
|
# product of 0 to a[i - 1]
|
||
|
|
prefix = 1
|
||
|
|
for i, num in enumerate(nums):
|
||
|
|
result[i] = prefix
|
||
|
|
prefix *= num
|
||
|
|
|
||
|
|
# Find suffix products by iterating from the last, and
|
||
|
|
# combine them with prefix in the same step to reduce cost
|
||
|
|
suffix = 1
|
||
|
|
for i in range(len(nums) - 1, -1, -1):
|
||
|
|
result[i] *= suffix
|
||
|
|
suffix *= nums[i]
|
||
|
|
|
||
|
|
return result
|
||
|
|
|