238. Product of Array Except Self

Approach 1: Calculate products from both sides

In a single for loop keep multiplying terms from left side and right side respectively and multiply those two to get the required product

class Solution(object):
    def productExceptSelf(self, nums):
        """
        https://leetcode.com/problems/product-of-array-except-self/description/
        :type nums: List[int]
        :rtype: List[int]
        """
        result = [1] * len(nums)
        leftsum = 1
        rightsum = 1
        for i in range(len(nums)):
            result[i] *= leftsum
            result[len(nums)-i-1] *= rightsum
            leftsum *= nums[i]
            rightsum *= nums[len(nums)-i-1]
        return result

Time Complexity: O(N)

Space Complexity: O(1)

Approach 2: Calculate products from both sides in 2 arrays

In a single loop build 2 arrays that contain the product of all the numbers to the left of a position, and all the numbers to the right of a position. Once those arrays are constructed, you can simply iterate through these index by index and multiply the left product at the previous index, and the right product at the next index to build the array of required products

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        le = len(nums)
        dp_left, dp_right = [1]*(le+1), [1]*(le+1)
        for i in range(le):
            dp_left[i+1] *= dp_left[i] * nums[i]
            dp_right[le - i - 1] = dp_right[le - i] * nums[-1 * i - 1]
        
        ans = []
        for i in range(le):
            ans.append(dp_left[i]*dp_right[i+1])
        return ans

Time Complexity: O(N)

Space Complexity: O(N)

Illegal Approach: Division

def productExceptSelf(nums):
    """
    https://leetcode.com/problems/product-of-array-except-self/#/description
    :type nums: List[int]
    :rtype: List[int]
    """
    product=1
    for num in nums:
        if num==0:
            product=0
            break
        product=product*num
    if product==0:
        return [0]*len(nums)
    return [int(product/x) for x in nums]

Time Complexity: O(N)

Space Complexity: O(1)