## 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 = [1] * 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 = [1] * 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
# (already stored at i).
right = 1
for i in range(n-1, -1, -1):
out[i] *= right
right *= nums[i]
return out
```