#### Day 2

Here is our given problem,

Given an array `nums` of n integers where n > 1,  return an array `output` such that `output[i]` is equal to the product of all the elements of `nums` except `nums[i]`.

Example:

```Input:  `[1,2,3,4]`
Output: `[24,12,8,6]`
```

Note: Please solve it without division and in O(n).

Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)

## Problem Explanation

### Product of Array except self

In the above example of arr = [1, 2, 3, 4],

For every element, store the product of array elements except the element which you currently point.

That is, at element 1, store the product of array elements, except 1st element. Except 1, then remaining elements are 2, 3 and 4. Multiply these elements and store it in 1th element position, that’s 24.

At element 1, store the product of array elements, except 2nd element. Except 2, then remaining elements are 1, 3 and 4. Multiply these elements and store it in 2th element position, that’s 12.

At element 3, store the product of array elements, except 3rd element. Except 3, then remaining elements are 1, 2 and 4. Multiply these elements and store it in 1th element position, that’s 8.

At element 4, store the product of array elements, except 4th element. Except 4, then remaining elements are 1, 2 and 3. Multiply these elements and store it in 4th element position, that’s 6.

## Approach 1

The easier way to solve this problem by using two arrays, leftArray and rightArray.

### leftArray

In leftArray store the product of element values from left. There is no element present left side of the index 0th position,. So put constant value 1 there.

At element 2, the product of left elements value is 1.

At element 3, the product of left elements value is 2.

At element 4, the product of left elements value is 6.

### rightarray

In rightArray store the product of element values from right. There is no element present right side of the index (n-1)th position,. So put constant value 1 there.

Now just imagine, we have leftArray which contains all the product of left elements value except self and rightArray which contains all the product of right elements values except self.

Similarly for each other elements also. Multiply left[i] with right[i] to get our desired result of product of array elements except self.

But this won’t solve our problem, because, in our given question, they asked us to solve the problem in O(1) space complexity, that is constant space. So going to approach 2.

## Approach 2

We need to reduce the space complexity. When you think deeply, you can able to agree that, we no need rightArray. We can use the simple variable, to do the rightArray task.

### leftarray

```
//left array which contains the product of elements to the right
int[] leftArray = new int[nums.length];

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

### Right “R” Variable

1. R contains the product of all the elements to the right
2. For the element at index ‘length – 1’, there are no elements to the right, so the R would be 1.
```        int R = 1;
for(int i=nums.length-1;i>=0;i--)
{
// For the index 'i', R would contain the
// product of all elements to the right. We update R accordingly
//Performing rightArray task using simple R variable, so we reducing O(n) extra space
leftArray[i] = R * leftArray[i];
R = R * nums[i];
}
```

## Solution

```class Solution {
public int[] productExceptSelf(int[] nums) {

//left array which contains the product of elements to the right
int[] leftArray = new int[nums.length];

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

int R = 1;
for(int i=nums.length-1;i>=0;i--)
{
// For the index 'i', R would contain the
// product of all elements to the right. We update R accordingly
leftArray[i] = R * leftArray[i];
R = R * nums[i];
}

return leftArray;
}
}
```

Time Complexity : O(n)

Space Complexity : O(1) Constant space

#### Note:

If you like to join with me, please follow me via email. So that, whenever I solve problems and update here, you will get an email notification message.

Processing…
Success! You're on the list.