class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        ans = [1] * len(nums)
        
        # forward
        prefix = 1
        for i in range(len(nums)):
            ans[i] *= prefix
            prefix *= nums[i]

        # backward
        suffix = 1
        for i in range(len(nums)-1, -1, -1):
            ans[i] *= suffix
            suffix *= nums[i]

        return ans

class Solution:
    def productExceptSelf(self, nums: List[int]) -> List[int]:
        if not nums:
            return []

        result = [1 for _ in range(len(nums))]

        prefix_product = 1
        for i in range(len(nums)):
            result[i] *= prefix_product # first *= 1
            prefix_product *= nums[i]                        

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

        return result