238. Product of Array Except Self

Medium

Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Constraint: It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer. Note: Please solve it without division and in O(n). Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

😇 Solution

O(n)

class Solution:   
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        
        l = len(nums)
        
        left = [0 for _ in range(l)]
        left[0] = 1
        for i in range(1,l):
            left[i] = nums[i-1]*left[i-1]
            
        right = [0 for _ in range(l)]
        right[l-1] = 1
        for i in reversed(range(l-1)):
            right[i] = nums[i+1]*right[i+1]
        
        ans = []
        for i in range(l):
            ans.append(left[i]*right[i])
            
        return ans

O(n2)

class Solution:
    def product(nums):
        p = 1
        for n in nums:
            p *= n
        return p
    
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = []
        for i in range(len(nums)):
            ans.append(Solution.product(nums[:i]+nums[i+1:]))
        return ans