# [Product of Array Except Self](https://leetcode.com/problems/product-of-array-except-self/)
###### tags: `Leetcode`, `Medium`, `Arrays and Hashing`

## Approach
* Initialize two lists:
* PreFixArray: This will have the same length as the input array. At every index position this list will have the product of all the numbers occuring before it in the input array
* PostFixArray: This will have the same length as the input array. At every index position this list will have the product of all the numbers occuring after it in the input array
* In the result array at every index position add the product of the numbers at the same index position in PreFixArray and PostFixArray
* Return the result array

### O(1) Space Complexity Solution
* Same approach as the previous one but instead of initializing the pre and post fix arrays, do it on the fly in the result array

## Asymptotic Analysis
### Time Complexity: **O(N)**
### Space Complexity: **O(N)**

## Code

from typing import List


class ProductOfArrayExceptSelf:

    @staticmethod
    def product_except_self_linear_space(numbers: List[int]) -> List[int]:
        postfix, prefix = [1] * len(numbers), [1] * len(numbers)
        result = [1] * len(numbers)

        # Populate prefix list
        for index in range(1, len(numbers)):
            prefix[index] = numbers[index - 1] * prefix[index - 1]

        # Populate postfix list
        for index in range(len(numbers) - 2, -1, -1):
            postfix[index] = numbers[index + 1] * postfix[index + 1]

        # Populate result list
        for index in range(len(numbers)):
            result[index] = prefix[index] * postfix[index]

        return result

    @staticmethod
    def product_except_self_constant_space(numbers: List[int]) -> List[int]:
        prefix, postfix = 1, 1
        result = [1] * len(numbers)

        # Populate prefix result
        for index in range(len(numbers)):
            result[index] = prefix
            prefix *= numbers[index]

        # Populate postfix result
        for index in range(len(numbers) - 1, -1, -1):
            result[index] *= postfix
            postfix *= numbers[index]

        return result


nums = [1, 2, 3, 4]
print(ProductOfArrayExceptSelf.product_except_self_linear_space(nums))
print(ProductOfArrayExceptSelf.product_except_self_constant_space(nums))