LeetCode 238. Product of Array Except Self

Intuition

Original Intuition was creating 3 arr

1. pre that keeps track of prefix multiplication
2. post that keeps track of postfix multiplication
3. res that keeps track of results
4. compute result using pre times post Further optimization is possible by doing this inplace
5. use res as a prefix arr and multiply postfix elements in the second loop

Optimal Solution

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:

        res = [1] * len(nums) 
        # compute pre
        curr = 1
        for i in range(len(nums)):
            res[i] = curr
            curr *= nums[i]
        curr = 1

        # compute post
        for i in range(len(nums)-1,-1,-1):
            res[i] *= curr
            curr *= nums[i]

        return res

Time Complexity

Time Complexity O(N)

Space Complexity O(N)