Leetcode 238. Product of Array Except Self

238. Product of Array Except Self

Implication : First multiply the numbers literately from left side, then do it again from right side.

Reference Solution


First thought with O(n) space complexity :

leetcode238-1 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        leftSideMultiply = [1]
        rightSideMultiply = [1]
        n = len(nums)
        
        # Implication : First multiply the numbers literately from left side, then do it again from right side.
        for i in range(n) :
            leftSideMultiply.append( leftSideMultiply[i] * nums[i] )
            rightSideMultiply.append( rightSideMultiply[i] * nums[n - i - 1] )
        
        result = []        
        for i in range(n) :
            result.append( leftSideMultiply[i] * rightSideMultiply[n - i - 1] )
            
        return result

To improve, we can reuse the result array :

leetcode238-2 

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        result = [1]
        n = len(nums)
        for i in range(n) :
            # Step 1 : multiply the numbers literately from left side.
            result.append( result[i] * nums[i] ) 
            
        temp = 1
        for i in range(n,0,-1) :
            # Step 2 : multiply from right side and save the product in temp.
            result[i] = result[i-1] * temp
            
            # Step 3 : update temp.
            temp *= nums[i-1]
            
        return result[1:]