# Product of Array Except Self

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

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

**Code: with extra space:**&#x20;

```python
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        m = collections.defaultdict(list)
        p = 1
        for i, num in enumerate(nums):
            m[i] = p
            p *= num

        p = 1

        for i, num in reversed(list(enumerate(nums))):
            m[i] *= p
            p *= num

        return [m[k] for k in sorted(m.keys())]
```

**Code: without extra space:**

```java
class Solution {
    public int[] productExceptSelf(int[] nums) {
        int n = nums.length;
        int res [] = new int [n];
        int p = 1;

        // multiply left
        for(int i = 0; i < n; i++){
            res[i] = p;
            p *= nums[i];
        }

        // multiply right
        p = 1;
        for(int i = n - 1; i >=0 ; i--){
            res[i]*= p;
            p *= nums[i];
        }

        return res;
    }
}
```

**Code: actually index is the key: so we do not need the extra dictionary**

```python
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        # m = collections.defaultdict(list)
        res = [0] * len(nums)
        p = 1
        # left
        for i, num in enumerate(nums):
            res[i] = p
            p *= num

        p = 1

        for i, num in reversed(list(enumerate(nums))): # i is also reversed
            res[i] *= p
            p *= num

        return res
```
