Product of Array Except Self (Leetcode #238)

Given an integer array nums, return an arrayanswersuch thatanswer[i]is equal to the product of all the elements ofnumsexceptnums[i].

The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

You must write an algorithm that runs in O(n) time and without using the division operation.

Example 1:

Input: nums = [1,2,3,4]
Output: [24,12,8,6]

Example 2:

Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]

Constraints:

• 2 <= nums.length <= 10<sup>5</sup>

• -30 <= nums[i] <= 30

• The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

Follow up: Can you solve the problem in O(1) extra space complexity? (The output array does not count as extra space for space complexity analysis.)

Answer:

The simplest solution to this question would be to get the product of this array loop through this one and divide the total product to get the product of the array except self. But since the question asked us not to use division sign we have to use other method to get the answer.

Optimal Solution:

Create two loop one of a prefix product and one of the postfix product by doing this we will be able to get the sum product of the entire array without using division as well as do it in O(N) time complexity. Also, if we manipulate the answer directly into the output we will also be able to reduce the time complexity down to O(1)

class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        ans = [1] * n

        # Compute the prefix products and store them in ans
        prefix = 1
        for i in range(n):
            ans[i] = prefix
            prefix *= nums[i]

        # Compute the postfix products and multiply them with the prefix products stored in ans
        postfix = 1
        for i in range(n - 1, -1, -1):
            ans[i] *= postfix
            postfix *= nums[i]

        return ans

Time complexity:

O(N) Since we looping through the list twice

Space Complexity:
O(1) since we are only creating the answer list of length n