[LeetCode][python3]Day15. Product of Array Except Self (30-Day LeetCoding Challenge)

30 days! Lets go Lets go!
N2I -2020.04.16

1. My Solution

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res=[0]*len(nums)
        res[-1]=nums[-1]
        for i in range(1,len(nums)):
            res[len(nums)-i-1]=res[len(nums)-i]*nums[len(nums)-i-1]
        prefix=1
        for i in range(len(nums)-1):
            res[i]=prefix*res[i+1]
            prefix*=nums[i]
        res[-1]=prefix
        return res

Explanation:

The Solution is under the rule “Please solve it without division and in O(n)”.

2. A Clean Solution

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        curr = 1
        result = []
        for num in nums:
            result.append(curr)
            curr *= num
        curr = 1
        for i in range(len(nums)-1, -1, -1):
            result[i] *= curr
            curr *= nums[i]
        return result