# Product of Array Except Self (Leetcode #238)

[Given an integer array `nums`, return *an array*`answer`*such that*`answe`](https://leetcode.com/problems/product-of-array-except-self/)`r[i]`*is equal to the product of all the elements of*`nums`*except*`nums[i]`.

The product of any prefix or suffi[x of `nums` is **guaranteed** to fit in](https://leetcode.com/problems/product-of-array-except-self/) a **32-bit** integer.

You must write an algorithm that r[uns in `O(n)` time and without usin](https://leetcode.com/problems/product-of-array-except-self/)g the division operation.

**Example 1:**

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

[**Example 2**](https://leetcode.com/problems/product-of-array-except-self/)**:**

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

[**Co**](https://leetcode.com/problems/product-of-array-except-self/)**nstraints:**

* `2 <= nums.lengt`[`h <= 10<sup>5</sup>`](https://leetcode.com/problems/product-of-array-except-self/)
    
* [`-30 <= nums[i] <= 30`](https://leetcode.com/problems/product-of-array-except-self/)
    
* [The product of any prefix or suffix of `nums` is **guaranteed** to fit in](https://leetcode.com/problems/product-of-array-except-self/) a **32-bit** integer.
    

**Follow up:** Can you solve the pr[oblem in `O(1)` extra space complexity](https://leetcode.com/problems/product-of-array-except-self/)? (The output array **does not** count as extra space for space complexity analysis.)

### **Answer:**

The simplest solution to this question would be to get the product of this array loop through this one and divide the total product to get the product of the array except self. But since the question asked us not to use division sign we have to use other method to get the answer.

**Optimal Solution:**

Create two loop one of a prefix product and one of the postfix product by doing this we will be able to get the sum product of the entire array without using division as well as do it in O(N) time complexity. Also, if we manipulate the answer directly into the output we will also be able to reduce the time complexity down to O(1)

```python
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        n = len(nums)
        ans = [1] * n

        # Compute the prefix products and store them in ans
        prefix = 1
        for i in range(n):
            ans[i] = prefix
            prefix *= nums[i]

        # Compute the postfix products and multiply them with the prefix products stored in ans
        postfix = 1
        for i in range(n - 1, -1, -1):
            ans[i] *= postfix
            postfix *= nums[i]

        return ans
```

**Time complexity:**

O(N) Since we looping through the list twice

**Space Complexity:**  
O(1) since we are only creating the answer list of length n