# https://[Log in to view URL]
# Given an integer array nums, return an array answer such that answer[i] is equal to the product of all the elements of nums except nums[i].

# The product of any prefix or suffix of nums is guaranteed to fit in a 32-bit integer.

# You must write an algorithm that runs in O(n) time and without using the division operation.

# Example 1:

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

# Example 2:

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

# Solution 1: brute force, not acceptable 

# Solution 2: maintain a list of prefix products and suffix products that exclude the element at that position, like this:
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        prefix = [1 for _ in nums]
        suffix = [1 for _ in nums]
        result = [0 for _ in nums]

        for i in range(1, len(nums)):
            prefix[i] = prefix[i - 1] * nums[i - 1]

        for i in range(len(nums) - 2, -1, -1):
            suffix[i] = suffix[i + 1] * nums[i + 1]

        for i in range(len(nums)):
            result[i] = prefix[i] * suffix[i]

        return result

# Solution 3: there can be a running prefix which is computed in either direction; with only the result array being stored.
class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        prefix = 1
        suffix = 1
        result = [1] * len(nums)

        for i in range(1, len(nums)):
            prefix = prefix * nums[i - 1]
            result[i] = prefix

        for i in range(len(nums) - 2, -1, -1):
            suffix = suffix * nums[i + 1]
            result[i] *= suffix

        return result