\
Given an [integer](https://en.wikipedia.org/wiki/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  `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:**

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

**Example 2:**

```javascript
Input: nums = [-1,1,0,-3,3]
Output: [0,0,9,0,0]
```

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

**Solution:**

The main trick here is  `O(n) time and without using the division operation.`

I will try to draw the main idea.

\
I will use extra space in this solution, but we can improve the algorithm later and remove additional memory.

\
> We will multiply elements from the left to the right and then from the right to the end exept self element

\
What if we prepare leftArr and multiply elements from the left to the right side.

\
```javascript
0. nums    = [1,2,3,4]
1. leftArr = [1,1,1,1]
2. leftArr = [1,1,1*2,1*2*3]
3. leftArr = [1,1,2,6]
```

\
Then we can prepare rightArr and multiply elements from the right to the left side.

\
```javascript
0. nums     = [1,2,3,4]
1. rightArr = [1,1,1,1]
2. rightArr = [1,1,1*4,1]
3. rightArr = [1,1*3*4,4,1]
3. rightArr = [1*2*3*4,1*3*4,4,1]
4. rightArr = [24,12,4,1]
```

\
And then, we should iterate over two arrays and multiply the elements

\
```javascript
0. leftArr = [1,1,2,6]
1. leftArr = [24,12,4,1]
2. rez     = [24, 12, 8, 6]
```

\
Seems like a wise decision, doesn’t it?

\
And of course, the code for it.

```
public int[] productExceptSelf(int[] nums) {
    int length = nums.length;
    int[] toRight = new int[length];
    int[] toLeft = new int[length];
    toRight[0] = 1;
    for(int i = 1; i < length; i++){
        toRight[i] = toRight[i-1] * nums[i-1];
    }
    toLeft[length - 1] = 1;
    for(int i = length - 2; i >= 0; i--){
        toLeft[i] = toLeft[i+1] * nums[i+1];
    }
    
    for(int i = 0; i < length; i++){
        toRight[i] = toRight[i] * toLeft[i];
    }
    return toRight;
}
```

\
> Using this approach, we can find a sum or multiply elements in the arrays without using ‘+‘ or ‘\*‘
>
> operation.

\
But how can we improve it?

For now, we use two other arrays, and that is fine. Let’s try to reduce memory complexity.

Without creating two arrays, we can make only one array. Again, iterate over the base array and multiply elements from the left to the right side.

\
```javascript
    public int[] productExceptSelf(int[] nums) {
        int[] ans = new int[nums.length];
        int left = 1;
        
        for (int i = 0; i < nums.length; i++) {
            ans[i] = left;
            left *= nums[i];
        }
        
        int right = 1;
        for (int i = nums.length - 1; i >= 0; i--) {
            ans[i] *= right;
            right *= nums[i];
        }
        
        return ans;
    }
```

\
*Runtime: 1 ms, faster than 100.00% of Java online submissions for Product of Array Except Self. \n Memory Usage: 50 MB, less than 59.22% of Java online submissions for Product of Array Except Self*

\
>  \n **The concept is simple, you want to calculate the products from both left side and right side (excluding itself). The ans\[i\] is left \* right.**

\
I hope it was clear for you guys. Please write comments if something is unclear for you, and I will try to answer.

\
And yes, this problem is so prevalent in a lot of companies.

 ![](https://cdn.hackernoon.com/images/WyL2V0Nj20amUlioe5bpd0cPHF92-7p93pto.png)

[Leetcode solution.](https://leetcode.com/problems/product-of-array-except-self/)

\
\


This story contains new, firsthand information uncovered by the writer.

2021 - HackerNoon Contributor of the Year - INNOVATION

2022 - HackerNoon Contributor of the Year - Design

2022 - HackerNoon Contributor of the Year - Software Architecture

2021 - HackerNoon Contributor of the Year - COMPUTER-SCIENCE

2021 - Rick Sanchez of the Year

Nominated for 2022 - HackerNoon Contributor of the Year - Design

Nominated for 2022 - HackerNoon Contributor of the Year - Software Architecture

Too Long; Didn't Read

Cassandra Forward a free Cassandra-focused community event

Finding Product of Array Except Self

Too Long; Didn't Read

@deft

Credibility

RELATED STORIES