## Problem Statement#

### 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.

### Examples#

#### 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 <= 105`
• `-30 <= nums[i] <= 30`
• The product of any prefix or suffix of `nums` is guaranteed to fit in a 32-bit integer.

## Key Insights#

We can solve this problem in two passes to achieve an `O(N)` runtime. In the first forward pass, we calculate the left prefix multiple and store it an `out` list. (We store the product of the elements before index `i` at each index `i`). In the second reverse pass, we maintain a `right` variable that keeps track of the right suffix multiple. As we iterate backwards through the `out` list we update the value at index `i` with the product of the left prefix multiple (stored at index `i`) and the right suffix multiple (the `right` variable).

## Python Solution#

### Brute Force (TLE)#

``````class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
"""
T: O(N^2)
S: O(N)
"""
n = len(nums)
out =  * n

# Note: This approach will
#       experience a time
#       limit exception (TLE)
#       on Leetcode.
#
# The outer for loop iterates
# from 0 to n - 1.
# The inner for loop iterates
# from i + 1 to n - 1.
# The "left" variable keeps
# track of the product of all
# elements before i, and
# "right" keep track of the
# product all elements to the
# right of i.

left = 1
# Iterate through nums
for i in range(n):

# calculate right product
right = 1
for j in range(i + 1, n):
right *= nums[j]

# Calculate product excluding self
out[i] = right * left

# Calculate left product
left *= nums[i]

return out
``````

### Optimized#

``````class Solution:
def productExceptSelf(self, nums: List[int]) -> List[int]:
"""
T: O(N)
S: O(N)

nums = [1,  2,  3,  4]

# first pass
out  = [1,  1,  2,  6]
^

# second pass
right = 24
out  = [24, 12, 8,  6]
^

"""
n = len(nums)
out =  * n

# Calculate the product of all
# elements to the left of i and
# save the results in the out
# list.
left = 1
for i in range(n):
out[i] = left
left *= nums[i]

# Loop backwards from the end and
# calculate the product of all
# elements to the right of i
# and multiply it by the product
# of all elements to the left