## Problem

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]
```

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

## Solving with Two Arrays

To solve the problem, we can use two arrays: one to store the `left`

products and another to store the `right`

products. The product at each index is calculated by multiplying the products before and after that index.

```
prod = (left products) X (right products);
```

First, let’s focus on the left product. Assuming we have an array called `nums`

with values `[0, 1, 2, 3]`

, here’s how the left products would look for each index:

```
left[1] = 0;
left[2] = 0 * 1;
left[3] = 0 * 1 * 2;
```

We can observe that the left product at index `i`

is equal to the product of the left product at index `i-1`

multiplied by the number at index `i-1`

. Therefore:

```
left[i] = left[i-1] * nums[i-1];
```

We can use a similar concept to generate the right products:

```
right[i] = right[i+1] * nums[i+1];
```

Finally, to get the product at a specific index `i`

, we multiply the corresponding left and right products:

```
prod[i] = left[i] * right[i];
```

Here’s the code:

```
var productExceptSelf = function(nums) {
const left = [1];
for (let i = 1; i < nums.length; i++) {
left[i] = nums[i-1] * left[i-1];
}
const right = [];
right[nums.length-1] = 1;
for (let i = nums.length - 2; i >= 0; i--) {
right[i] = nums[i+1] * right[i+1];
}
const res = [];
for (let i = 0; i < nums.length; i++) {
res[i] = left[i] * right[i];
}
return res;
};
```

This solution has a time and space complexity of `O(N)`

.

## Optimizing Space

The problem has a follow-up:

Can you solve the problem in

`O(1)`

extra space complexity? (The output array does not count as extra space for space complexity analysis.)

We used two arrays to hold the `left`

and `right`

products, and we need to solve the problem without using these arrays.

The output array does not count as extra space, so we can utilize it to temporarily store the `left`

or `right`

products. In this case, let’s use the output array to hold the `left`

products.

Now that we have handled the `left`

products, let’s figure out how to calculate the `right`

products. Given the example array `nums = [0, 1, 2, 3]`

, the right products can be calculated as follows:

```
right[2] = 3;
right[1] = 3 * 2;
right[0] = 3 * 2 * 1;
```

We can observe that the `right`

product can be obtained by multiplying the current `right`

product with the number at the next index. Therefore:

```
right = 3;
right = right * 2;
right = right * 1;
...
right = right * nums[i+1];
```

By using a single variable `right`

, we can calculate the `right`

products without using an additional array, resulting in `O(1)`

space complexity.

Here’s the code for the optimized solution:

```
var productExceptSelf = function(nums) {
const res = [1];
for (let i = 1; i < nums.length; i++) {
res[i] = nums[i-1] * res[i-1];
}
let right = 1;
for (let i = nums.length-2; i >= 0; i--) {
right *= nums[i+1];
res[i] *= right;
}
return res;
};
```

This optimized solution still maintains `O(N)`

time complexity but reduces the space complexity to `O(1)`

.