# LeetCode - Product of Array Except Self

## Problem statement

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.

Problem statement taken from: https://leetcode.com/problems/product-of-array-except-self

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

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

### Explanation

#### Brute force approach

As per the problem statement, we cannot use the division operator. The first approach we can think off is to use two nested for loops and multiple the two numbers when indexes does not match.

A small C++ snippet of the above solution will look as below:

```
vector<int> answer(nums.size(), 0);
for(int i = 0; i < nums.size(); i++){
product = 1;
for(int j = 0; j < nums.size(); j++){
if(i != j){
product *= nums[j];
}
}
answer[i] = product;
}
```

The issue with the above approach is the time complexity.
The time complexity of the above approach is **O(N^2)**.

#### Linear approach

We can optimize the above solution to **O(N)** by evaluating
the products of the element from left to right and
from right to left.

Let's check the algorithm

```
- initialize vector<int>answer, i
- set product = 1
- loop for i = 0; i < nums.size(); i++
- append answer.push_back(product)
- set product = product * nums[i]
- reset product = 1
- loop for i = nums.size() - 1; i >= 0; i--
- set answer[i] = answer[i]*product
- product *= nums[i]
- return answer
```

#### C++ solution

```
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
vector<int> answer;
int product = 1, i;
for(i = 0; i < nums.size(); i++){
answer.push_back(product);
product *= nums[i];
}
product = 1;
for(i = nums.size() - 1; i >= 0; i--){
answer[i] *= product;
product *= nums[i];
}
return answer;
}
};
```

#### Golang solution

```
func productExceptSelf(nums []int) []int {
answer := make([]int, len(nums))
product := 1
for i := 0; i < len(nums); i++ {
answer[i] = product
product *= nums[i]
}
product = 1
for i := len(nums) - 1; i >= 0; i-- {
answer[i] *= product
product *= nums[i]
}
return answer
}
```

#### Javascript solution

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

#### Dry Run

Let's dry-run our algorithm to see how the solution works.

```
Input: nums = [1, 2, 3, 4]
Step 1: vector<int> answer
int product = 1, i
Step 2: loop for i = 0; i < nums.size()
0 < 4
true
answer.push_back(product)
answer.push_back(1)
answer = [1]
product *= nums[i]
product = product * nums[0]
= 1 * 1
= 1
i++
i = 1
Step 3: loop for i < nums.size()
1 < 4
true
answer.push_back(product)
answer.push_back(1)
answer = [1, 1]
product *= nums[i]
product = product * nums[1]
= 1 * 2
= 2
i++
i = 2
Step 4: loop for i < nums.size()
2 < 4
true
answer.push_back(product)
answer.push_back(2)
answer = [1, 1, 2]
product *= nums[i]
product = product * nums[2]
= 2 * 3
= 6
i++
i = 3
Step 5: loop for i < nums.size()
3 < 4
true
answer.push_back(product)
answer.push_back(6)
answer = [1, 1, 2, 6]
product *= nums[i]
product = product * nums[3]
= 6 * 4
= 24
i++
i = 4
Step 6: loop for i < nums.size()
4 < 4
false
Step 7: product = 1
Step 8: loop for i = nums.size() - 1; i >= 0
i = 4 - 1 = 3
i >= 0
3 >= 0
true
answer[i] *= product
= answer[3] * product
= 6 * 1
= 6
product *= nums[i]
= product * nums[3]
= 1 * 4
= 4
i--
i = 2
Step 9: loop for i >= 0
2 >= 0
true
answer[i] *= product
= answer[2] * product
= 2 * 4
= 8
product *= nums[i]
= product * nums[2]
= 4 * 3
= 12
i--
i = 1
Step 10: loop for i >= 0
1 >= 0
true
answer[i] *= product
= answer[1] * product
= 1 * 12
= 12
product *= nums[i]
= product * nums[1]
= 12 * 2
= 24
i--
i = 0
Step 11: loop for i >= 0
0 >= 0
true
answer[i] *= product
= answer[0] * product
= 1 * 24
= 24
product *= nums[i]
= product * nums[0]
= 24 * 1
= 24
i--
i = -1
Step 12: loop for i >= 0
-1 >= 0
false
Step 13: return answer
So the answer is [24, 12, 8, 6]
```