---
tags: data_structure_python
---

# Product of Array Except Self <img src="https://img.shields.io/badge/-medium-orange">

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].

<ins>**Example:**</ins>

Input:  [1,2,3,4]
Output: [24,12,8,6]

**Constraint:** It's guaranteed that the product of the elements of any prefix or suffix of the array (including the whole array) fits in a 32 bit integer.

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

# Solution

### Solution 1: First approach

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # O(n) in time complexity.
        # O(n) in space complexity
        n = len(nums)
        
        left_cum_prod = [1]
        for i in range(n-1):
            left_cum_prod.append(left_cum_prod[i] * nums[i])
        
        right_cum_prod = [1]
        for i in range(n-1):
            right_cum_prod.append(right_cum_prod[i] * nums[n-1-i])
            
        return [left_cum_prod[i] * right_cum_prod[n-1-i] for i in range(n)]

### Solution 2: Second approach

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        # O(n) in time complexity.
        # O(1) in space complexity
        n = len(nums)
        
        left_cum_prod = [1]
        for i in range(n-1):
            left_cum_prod.append(left_cum_prod[i] * nums[i])
        
        # Do it in-place instead of using right_cum_prod
        right_cum_prod = 1
        for i in range(1, n):
            left_cum_prod[n-1-i] *= right_cum_prod * nums[n-i]
            right_cum_prod *= nums[n-i]
        
        """
         nums = [1, 2, 3, 4]
            L = [1, 1, 2, 6]
            
            L[3]               = 6
            L[2] = 2 * (1 * 4) = 8
            L[1] = 1 * (4 * 3) = 12
            L[0] = 1 * (12* 2) = 24            
        """
            
        return left_cum_prod

### Solution 3: Third approach

- Same idea as solution 2 but cleaner

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        res = [1]
        for i, elt in enumerate(nums[:-1]):
            res.append(res[i] * elt)
         
        R, n = 1, len(res)
        for i, elt in enumerate(nums[::-1]):
            res[n-1-i] *= R
            R *= elt
            
        return res