238. Product of Array Except Self

Code

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

Intuition

The approach used in this code is based on the observation that the product of all the elements to the left of a given index i can be computed by taking the product of all the elements to the left of i-1 and multiplying it with the element at index i-1. Similarly, the product of all the elements to the right of index i can be computed by taking the product of all the elements to the right of i+1 and multiplying it with the element at index i+1.

Approach

1. To implement this approach, the code first initializes an empty list res with the same length as the input list nums. It then initializes each element of res to 1. This is because, for each index i in nums, the output should be the product of all the elements in nums except for the element at index i. By initializing each element of res to 1, we can start by computing the product of all the elements to the left of i and then multiply that by the product of all the elements to the right of i.
2. The code then initializes two variables called prefix and postfix to 1. These variables will be used to compute the product of all the elements to the left and right of each index i in nums, respectively.
3. The first loop goes through each index i in nums and updates the corresponding element of res by multiplying it with prefix and then updating prefix to be the product of prefix and nums[i]. This computes the product of all the elements to the left of i.
4. The second loop goes through each index i in nums in reverse order and updates the corresponding element of res by multiplying it with postfix and then updating postfix to be the product of postfix and nums[i]. This computes the product of all the elements to the right of i.
5. Finally, the method returns the list res, which now contains the product of all the elements in nums except for each element at index i.

Time Complexity: O(n) where n is length of input list

Space Complexity: O(n) to store result