238. Product of Array Except Self

Solution:

  • need to do this in O(n) time complexity and cannot use the division operator.
  • basically we loop through the list from front to back keeping track of the previous products. we get the product of the left hand side of nums[i] when looping forward and get the product of the right hand side of nums[i] when looping backwards.
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ret = [1] * len(nums)

        prev = nums[0]
        for i in range(1, len(nums)):
            ret[i] *= prev
            prev *= nums[i]
            
        prev = nums[len(nums)-1]
        for i in range(len(nums)-2, -1, -1):
            ret[i] *= prev
            prev *= nums[i]
        return ret
Tags