# 238. Product of Array Except Self

## Approach 1: Calculate products from both sides

In a single for loop keep multiplying terms from left side and right side respectively and multiply those two to get the required product

```python
class Solution(object):
    def productExceptSelf(self, nums):
        """
        https://leetcode.com/problems/product-of-array-except-self/description/
        :type nums: List[int]
        :rtype: List[int]
        """
        result = [1] * len(nums)
        leftsum = 1
        rightsum = 1
        for i in range(len(nums)):
            result[i] *= leftsum
            result[len(nums)-i-1] *= rightsum
            leftsum *= nums[i]
            rightsum *= nums[len(nums)-i-1]
        return result
```

> **Time Complexity:** *O(N)*
>
> **Space Complexity:** *O(1)* 

## Approach 2: Calculate products from both sides in 2 arrays

In a single loop build 2 arrays that contain the product of all the numbers to the left of a position, and all the numbers to the right of a position. Once those arrays are constructed, you can simply iterate through these index by index and multiply the left product at the previous index, and the right product at the next index to build the array of required products

```python
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        le = len(nums)
        dp_left, dp_right = [1]*(le+1), [1]*(le+1)
        for i in range(le):
            dp_left[i+1] *= dp_left[i] * nums[i]
            dp_right[le - i - 1] = dp_right[le - i] * nums[-1 * i - 1]
        
        ans = []
        for i in range(le):
            ans.append(dp_left[i]*dp_right[i+1])
        return ans
```

> **Time Complexity:** *O(N)*
>
> **Space Complexity:** *O(N)* 

## Illegal Approach: Division

```python
def productExceptSelf(nums):
    """
    https://leetcode.com/problems/product-of-array-except-self/#/description
    :type nums: List[int]
    :rtype: List[int]
    """
    product=1
    for num in nums:
        if num==0:
            product=0
            break
        product=product*num
    if product==0:
        return [0]*len(nums)
    return [int(product/x) for x in nums]
```

> **Time Complexity:** *O(N)*
>
> **Space Complexity:** *O(1)*