# Leetcode: Product of Array Except Self

Product of Array Except Self

Similar Problems:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

Similar problem: Trapping Rain Water

• Solution:

General Thinkings:

```Two pass:
- From left to right, get partial results.
- Then from right to left, get final results.
```

We can use the similar two-pass idea to solve: Shortest Distance to a Character

Walk Through Testdata

```// Numbers:     2    3    4     5
// Lefts:            2  2*3 2*3*4
// Rights:  3*4*5  4*5    5
// Let's fill the empty with 1:

// Numbers:     2    3    4     5
// Lefts:       1    2  2*3 2*3*4
// Rights:  3*4*5  4*5    5     1
```
```// Blog link: https://code.dennyzhang.com/product-of-array-except-self
// Basic Ideas: leftrightpass
//
// Complexity: Time O(n), Space O(1)
func productExceptSelf(nums []int) []int {
res := make([]int, len(nums))
res[0] = 1
for product, i:=1, 1; i<len(nums); i++ {
product *= nums[i-1]
res[i] = product
}
for product, i:=1, len(nums)-2; i>=0; i-- {
product *= nums[i+1]
res[i] *= product
}
return res
}
```

Share It, If You Like It.