238.md

238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

my thoughts:

1. brutal force, time O(n^2)

2. record pre-product [] from left, and from right. at each i, the result is pre-product from left[i] * from right[i]. time O(n). space O(n)

3. iterate the array, if no 0, find overall product, each res is overall product/current num; if there is one 0, multiply everything else and put it at the idx of the 0, rest are all 0; if more than one 0, just return [0]*len[nums]

my solution:

**********172ms
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        tp = 1
        leftp = []
        for n in nums:
            leftp.append(tp)
            tp *= n
        tp = 1
        rightp = []
        for n in nums[::-1]:
            rightp.append(tp)
            tp *= n
        rightp.reverse()
        for i in range(len(nums)):
            leftp[i] *= rightp[i]
        return leftp
		
**********183ms
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        count = 0
        idx = -1
        i = 0
        l = len(nums)
        while i<l and count<2:
            if nums[i] == 0:
                count += 1
                idx = i
            i += 1
        if count == 2:
            return [0]*l
        if count == 1:
            res = [0]*l
            p_idx = 1
            for n in nums:
                if n != 0:
                    p_idx *= n
            res[idx] = p_idx
            return res
        else:
            tp = 1
            for n in nums:
                tp *= n
            res = []
            for n in nums:
                res.append(tp/n)
            return res
            

my comments:

from other ppl's solution:

1. I think this is the same as the pre-product, but it is faster, may be the direct mutation of an array is faster than generating new one, 139ms:
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        arr = [1]*len(nums)
        product = 1
        
        for i in range(0,len(nums)):
            arr[i] = product
            product = product*nums[i]
            #print arr[i]
        
        product = 1
        for j in range(len(nums)-1,-1,-1):
            arr[j] = product*arr[j]
            product = product*nums[j]
            
        return arr