Problem Description

Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[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]

My Idea

My initial idea was to create the results list initiated with 1s. Then loop over nums and for each n create a list mult that has the value of n in every position except n’s index in nums and multiply this list with res. This, however, results in a time complexity of O(n^2). The better solution would be to reduce the amount of calculations by calculating the results of multiplying all the elements to the left and to the right of every index i respectively and multiply the results. This results in a time complexity of O(n). If done using two arrays it has a space complexity of O(n), but this can be reduced to O(1) if the calculations are done directly in res.

My solution

#Optimal solution with time complexity of O(n) and space complexity of O(1)
def productExceptSelf(nums: list[int]) -> list[int]:
    l = len(nums)
    res = [1] * l
    left_product = 1
    for i in range(l):
        res[i] = left_product
        left_product *= nums[i]
    right_product = 1
    for i in range(l - 1, -1, -1):
        res[i] *= right_product
        right_product *= nums[i]
    return res

# Better solution with time and space complexity of O(n)
def productExceptSelfBetter(nums: list[int]) -> list[int]:
    l=len(nums)
    left = [1]*l
    right = [1]*l
    for i in range(1,l):
        left[i]=left[i-1]*nums[i-1]
    for i in range(l-2,-1,-1):
        right[i]=right[i+1]*nums[i+1]
    return [a*b for a,b in zip(left,right)]
# Initiial approach with time complexity O(n^2)
def productExceptSelfInitial(nums: list[int]) -> list[int]:
    l=len(nums)
    res=[1 for n in nums]
    for i,e in enumerate(nums):
        mult=[e]*l
        mult[i]=1
        res = [a*b for a,b in zip(res,mult)]
    return res