Leetcode 238. Product of Array Except Self

https://leetcode.com/problems/product-of-array-except-self/

Because division is not allowed, so we should use multiplying only. The thought is to scan twice, first multiply left side, second multiply right.

Solution:

# T:O(n) S:O(1)
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums: return []
            
        left_product = [1 for _ in xrange(len(nums))]
        for i in xrange(1, len(nums)):
            left_product[i] = left_product[i - 1] * nums[i - 1]
            
        right_product = 1
        for i in xrange(len(nums) - 2, -1, -1):
            right_product *= nums[i + 1]
            left_product[i] = left_product[i] * right_product

        return left_product

Run Time: 180 ms