238.Product of Array Except Self

Tags: [dp], [leftrightdp], [make_use_of_output_space]

Com: {fb}

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

Given an array ofnintegers wheren> 1,nums, return an arrayoutputsuch thatoutput[i]is equal to the product of all the elements ofnumsexceptnums[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.)

Solution: DP, Left Right DP

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums or len(nums) <= 1:
            # based on the problem description: Given an array of n integers where n > 1.
            raise ValueError('the input is invalid')

        size = len(nums)

        left_products = [0 for _ in xrange(size)]
        left_products[0] = nums[0]
        for i in xrange(1, size):
            left_products[i] = left_products[i - 1] * nums[i]

        right_products = [0 for _ in xrange(size)]
        right_products[-1] = nums[-1]
        for i in xrange(size - 2, -1, -1):
            right_products[i] = right_products[i + 1] * nums[i]

        result = [1 for _ in xrange(size)]
        for i in xrange(size):
            if i - 1 >= 0:
                result[i] *= left_products[i - 1]
            if i + 1 < size:
                result[i] *= right_products[i + 1]

        return result

Note:

• Time complexity = O(n), n is the number of elements in the given array.
• Space complexity = O(n), n is the number of elements in the given array.

Follow Up Solution: Make use of the output space

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        if not nums or len(nums) <= 1:
            # based on the problem description: Given an array of n integers where n > 1.
            raise ValueError('the input is invalid')

        size = len(nums)

        # Using the result to store the left products.
        result = [0 for _ in xrange(size)]
        result[0] = nums[0]
        for i in xrange(1, size):
            result[i] = result[i - 1] * nums[i]

        # Using the nums to store the right products.
        for i in xrange(size - 2, -1, -1):
            nums[i] = nums[i + 1] * nums[i]

        prev_left_total_product = 0
        left_total_product = 0
        for i in xrange(size):
            left_total_product = result[i]
            result[i] = 1
            if i - 1 >= 0:
                result[i] *= prev_left_total_product
            if i + 1 < size:
                result[i] *= nums[i + 1]

            prev_left_total_product = left_total_product

        return result

Revelation:

• Make the use of the 'result' container space.
• Using the 'result' to store the left products.
• Using the 'nums' to store the right products.

Note:

• Time complexity = O(n), n is the number of elements in the given array.
• Space complexity = O(1), not including the output space.