Question

Given an array nums of n integers, return an array output such that output[i] is equal to the product of all the elements of nums, except nums[i].

Note: The product of any prefix or suffix of an array A can be broken down into two parts: the product of all elements before (or after) index i, and the product of all elements after (or before) index i. To solve this problem, we can use two arrays to store the product of all elements before and after each index.

Implement the function productExceptSelf(nums: List[int]) -> List[int] to solve the problem.

Example

nums = [1, 2, 3, 4]
output = productExceptSelf(nums)

Output:

[24, 12, 8, 6]

Explanation

To solve this problem, we can use two arrays: left and right to store the product of all elements before and after each index.

Initially, we set left[0] = 1 and right[n-1] = 1, since there are no elements to the left of the first element and no elements to the right of the last element.

Then, we iterate through the array from left to right, calculating the product of the left prefix. We multiply left[i-1] with nums[i-1] to update left[i].

Next, we iterate through the array from right to left, calculating the product of the right suffix. We multiply right[i+1] with nums[i+1] to update right[i].

Finally, we iterate through the array and for each index i, we multiply left[i] with right[i] to get the product of all elements except nums[i] and store it in the output array.

At the end, we return the output array.

Answer

from typing import List

def productExceptSelf(nums: List[int]) -> List[int]:
    n = len(nums)
    output = [0] * n   # Create an array to store the output
    
    # Calculate the product of all elements to the left of each index
    left = [1] * n
    for i in range(1, n):
        left[i] = left[i-1] * nums[i-1]
    
    # Calculate the product of all elements to the right of each index
    right = [1] * n
    for i in range(n-2, -1, -1):
        right[i] = right[i+1] * nums[i+1]
    
    # Calculate the product of all elements except nums[i]
    for i in range(n):
        output[i] = left[i] * right[i]
    
    return output

The time complexity of this solution is O(n), where n is the length of the input array nums. The space complexity is O(n), as we are using two additional arrays left and right of size n to store the product of all elements to the left and right of each index.