# Product of Array Except Self LeetCode Solution

Difficulty Level Medium
Groupon Walmart Global techViews 22

## Problem Statement

Product of Array Except Self LeetCode Solution – 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

### Input:

nums = [1, 2, 3, 4]

[24, 12, 8, 6]

### Input:

nums = [-1, 1, 0, -3, 3]

[0, 0, 9, 0, 0]

## Explanation

The output array is the product of each element in the array except the number present at that index. ## Approach:

Before we look at the constraints, let’s just think of solving the problem as is.

At first glance, it becomes evident that we could easily solve this problem in one of two ways:

1. Calculate the product of every item in the array `nums`. Then create a `result` array of the same length as `nums`, such that for each item in the result `result[i] = product / nums[i]`. This is super simple and runs in `O(n)`.
2. Create a `result` array of the same size as `nums`. We can calculate the results array by:
```<span class="hljs-keyword">for</span> (int i = <span class="hljs-number">0</span>; i < nums.length; i++) {
results[i] = <span class="hljs-number">1</span>;
<span class="hljs-keyword">for</span> (int j = <span class="hljs-number">0</span>; j < nums.length; j++) {
<span class="hljs-keyword">if</span> (i != j) {
result[i] *= nums[j];
}
}
}```

Now, in this second attempt, what are we actually doing? For each item in the `nums` array, we manage to get the product of everything in `nums` but that item itself. How would we explain this a bit more mathematically? Let’s try to define how we calculate `results[i]`:
```<span class="hljs-function">For all i in the middle of <span class="hljs-title">nums</span> <span class="hljs-params">(i.e., not at either end)</span>:
results[i] </span>= nums[<span class="hljs-number">0</span>] * ...... * nums[i-<span class="hljs-number">1</span>] * nums[i + <span class="hljs-number">1</span>] * ...... * nums[nums.length - <span class="hljs-number">1</span>]

For i = <span class="hljs-number">0</span>:
results[i] = nums[i + <span class="hljs-number">1</span>] * ...... * nums[nums.length - <span class="hljs-number">1</span>]

For i = nums.length - <span class="hljs-number">1</span>:
results[i] = nums[<span class="hljs-number">0</span>] * ...... * nums[i-<span class="hljs-number">1</span>]```

Hopefully, this spells it out a bit better. Essentially, to get results[i], for any i, we calculate the product everything to the left and to the right of nums[i]. Keep this in mind for later!

### Insight

We know the constraints, and we need to come up with a solution!

#### Left and Right Products

Let’s say we have an array of integers: [1, 2, 3, 4, 5, 6, 7, 8]. Let’s calculate the product of all items except for the 4 (index = 3)

`1 * 2 * 3 * 5 * 6 * 7 * 8`

is how we would do that. This product is the product of everything to the left and to the right of 4. This is equivalent to doing:
`(1 * 2 * 3) * (5 * 6 * 7 * 8)`

This is the product of the left product (the product of everything on the left) and the right product (the product of everything on the right)
Now, for any i-th item in nums, we should be able to calculate the product of everything but itself, by multiplying its left and right product!

#### Finding the Left Products (and Right Products) can be done in O(n)!

Let’s try to calculate a left product array, such that for `left[i]` = the product of everything to the left of nums[i], using this example (`[1,2,3,4]`).

`left = 1` (There is nothing to the left of nums, so we set it to 1)
`left = 1` (1 is to the left of nums, so we set it to 1)
`left = 1 * 2`
`left = 1 * 2 * 3`

Look for the pattern in those products (There’s a pattern here!)
`left = 1 = left * 1 = left * nums`
`left = 1 * 2 = left * 2 = left * nums`
`left = 1 * 2 * 3 = left * 3 = left * nums`

The pattern: `left[i] = left[i-1] * nums[i-1]` !!!

We can show a similar situation for the right product array-> `right[i] = right[i+1] * nums[i+1]`

`right = 1` (There is nothing to the left of nums, so we set it to 1)
`right = 4` (4 is to the right of nums)
`right = 4 * 3`
`right = 4 * 3 * 2`

Look for the pattern in those products (There’s a pattern here!)
`right = 4 = right * 4 = right * nums`
`right = 4 * 3 = right * 3 = right * nums`
`right = 4 * 3 * 2 = right * 2 = right * nums`

#### Solution

Now that we know how to calculate the left product array and right product array, we can simply say that `results[i] = left[i] * right[i]`!!

## Code for Product of Array Except Self

### Java Program

```class Solution {
public int[] productExceptSelf(int[] nums) {
int[] left = new int[nums.length];

int[] right = new int[nums.length];

left = 1;
for (int i = 1; i < nums.length; i++) {
left[i] = left[i-1] * nums[i-1];
}

right[nums.length - 1] = 1;
for (int i = nums.length - 2; i >= 0; i--) {
right[i] = right[i+1] * nums[i+1];
}

int[] product = new int[nums.length];
for (int i = 0; i < product.length; i++) {
product[i] = left[i] * right[i];
}

return product;
}
}```

### C++ Program

```class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int n= nums.size();
vector<int> res(n);

res = nums;
for(int i=1;i<n;i++){
res[i] = res[i-1] * nums[i];
}

res[n-1] = res[n-2];
int r=1;
for(int i=n-1;i>0;i--){
res[i] = res[i-1] * r;
r *= nums[i];
}
res = r;

return res;
}
};```

## Complexity Analysis for Product of Array Except Self LeetCode Solution

Time Complexity: O(n)

Space Complexity: O(n)

Translate »