238.Product of Array Except Self

Given an array ofnintegers wheren> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[i].

Solve itwithout divisionand 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 arraydoes notcount as extra space for the purpose of space complexity analysis.)

Method 1 loop twice O(n) time, O(1) space.

• For each element, set the index of the return array as the product of all elements left to itself.
• Loop again backwards, multiply the current value by a culminating product from the right side.

class Solution(object):
    def productExceptSelf(self, nums):
        res = []
        prev = 1
        for i in xrange(len(nums)):
            res.append(prev)
            prev *= nums[i]

        prev = 1
        for i in xrange(len(nums)-1, -1, -1):
            res[i] = prev * res[i]
            prev  *= nums[i]
        return res