> For the complete documentation index, see [llms.txt](https://lei-d.gitbook.io/leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://lei-d.gitbook.io/leetcode/array/238product-of-array-except-self.md).

# 238\_Product of Array Except Self

Level: medium

tag: array

## Question

```
Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product 
of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

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

## ***Idea***

The output equals multiplication of elements on the left of **nums\[i]** and on the right of **nums\[i]**.

We are going to use two loops, one from left to right, one from right to left.

When we loop from left to right, we record the product of all the elements on the left, called **leftPro,** then append **leftPro** to the output.

When we loop from right to left, we record the product of all the elements on the right, called **rightPro**, then multiply it to the original output.

## ***Time complexity***

 $$O(n)$$ since there are two loops over each element.

## ***Space complexity***

$$O(n)$$

## Python solution

```python
class Solution(object):
    def productExceptSelf(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """
        output = [1]
        leftPro = 1
        rightPro = 1

        # loop from left to right (don't consider the first element)
        for i in range(1,len(nums)):
            leftPro *= nums[i-1]
            output.append(leftPro)

        # loop from right to left (don't consider the last element)        
        for j in range(len(nums)-2,-1,-1):
            rightPro *= nums[j+1]
            output[j] *= rightPro

        return output
```