permalink: /archive/posts/daily_leetcode_5/
date: Tue Sep 27 2022 00:00:00 GMT+0000 (Coordinated Universal Time)

238. Product of Array Except Self

Medium

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

My initial thought was to just iterate through our given array, create a temporary array with our index split out and then call reduce(a * b) on that, but that ends up violating the O(n) constraint (would be O(n^2) in this case.)

from functools import reduce

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = [None] * len(nums)
        
        for k in range(len(nums)):
            t = nums[:k:] + nums[k+1::]
            
            ans[k] = reduce(lambda a, b: a * b, t)
            
        return ans

I ended up with something a little more intuitive when I realized I didn't need to ignore the current index and I could just utilize a continually growing multiplicative factor for each iteration.

# from functools import reduce

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = [1] * len(nums)
        
        l = 1
        r = 1
        
        for k in range(len(nums)):
            ans[k] *= l
            l *= nums[k]
            ans[~k] *= r
            r *= nums[~k]
            
        return ans