238. Product of Array Except Self

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.

Solution

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ret = [1] * len(nums)
        currprod = 1
        for idx in range(len(nums)):
            ret[idx] *= currprod #no need for "*="
            currprod *= nums[idx]
        currprod = 1
        for idx in range(len(nums)-1, -1, -1):
            ret[idx] *= currprod
            currprod *= nums[idx]
        return ret

Time Complexity: O(n)

Space Complexity: O(n)

Explanation

If one pass is done where the curr prod is recorded in an additional array (lprod), and a second pass is done backwards (rprod). Then answer[i] value would simply be lprod[i] * rpord[i]. However, with a little thought, the neccessity for two seperate arrays evaporates. The answer array itself can be used.