> For the complete documentation index, see [llms.txt](https://code.taozirui.com/lc/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://code.taozirui.com/lc/fb-19/sec/product-of-array-except-self.md).

# 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:** 

```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
```