LC 0238 [M] Product of Array Except Self - ALawliet/algorithms GitHub Wiki

naive solution would be to use division

the trick is that the product at index i is the product of everything to the left * everything to the right

• array of 1s to hold product answer
• single bidirectional pass with 2 pointers i => l, j = -1-i => r
• mult to get the answer to the left so far, then mult the current num
• mult the answer to the right so far, then mult the current num

T: O(n)
T: O(1)

first pass

1 2 3 4
1*1 1*1 1*2 2*3 | 6*4
1   1   2   6
so index [3] is the product of the numbers before it [:3] = 1*2*3

---

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1] * len(nums)
        lp = rp = 1
        for l in range(len(nums)):
            r = -1-l
            res[l] *= lp ; lp *= nums[l]
            res[r] *= rp ; rp *= nums[r]
        return res

class Solution:
    def productExceptSelf(self, nums):
        n = len(nums)
        res = []

        # first loop: get product before the element
        lp = 1
        for l in range(n):
            res.append(lp)
            lp *= nums[l]

        # second loop: get product after the element and multiply by product before the element
        rp = 1
        for r in range(n-1,-1,-1):
            res[r] *= rp
            rp *= nums[r]

        return res