238_Product of Array Except Self

Level: medium

tag: array

Question

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.)

Idea

The output equals multiplication of elements on the left of nums[i] and on the right of nums[i].

We are going to use two loops, one from left to right, one from right to left.

When we loop from left to right, we record the product of all the elements on the left, called leftPro, then append leftPro to the output.

When we loop from right to left, we record the product of all the elements on the right, called rightPro, then multiply it to the original output.

Time complexity

$O(n)$ since there are two loops over each element.

Space complexity

$O(n)$

Python solution

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        output = [1]
        leftPro = 1
        rightPro = 1

        # loop from left to right (don't consider the first element)
        for i in range(1,len(nums)):
            leftPro *= nums[i-1]
            output.append(leftPro)

        # loop from right to left (don't consider the last element)        
        for j in range(len(nums)-2,-1,-1):
            rightPro *= nums[j+1]
            output[j] *= rightPro

        return output